洛谷P3327 [SDOI2015]约数个数和——莫比乌斯反演

深藏阁楼爱情的钟 2021-11-01 03:40 249阅读 0赞

# 约数个数和 #

## [题目链接][Link 1] ##

## 题解： ##

## ![1604661-20190730211251598-1387348056.png][] ##

# 思路： #

## 1.转换：将枚举i是x的倍数，j是y的倍数转换成枚举一个约数，有多少个数是其倍数，这样可以用[整除分块][Link 2]预处理 ##

## 整除分块： ##

**给定n，求（Σd=1n  ⌊n /d⌋）%998244353，n<=1e14**

**直接枚举会爆**

**考虑优化：**

**我们发现，⌊n/d⌋是有可能等于⌊n/(d+1)****⌋的**

**那我们为什么要重复算呢？ 直接加就好了！！**

**那也就是说，对于一个i，我们要找到一个j，使得⌊n/i⌋=⌊n/(i+1)⌋=⌊n/(i+2)⌋=……=⌊n/j⌋!=n/(j+1)**

**那么，我们得出 j=⌊n/(⌊n/i⌋)⌋**

**于是就可以优化了，复杂度是O（sqrt（n））**

## 2.由莫比乌斯的重要性质![1604661-20190730211800634-1140265610.png][]，将gcd(a,b)=k转换成gcd(a,b)/k=1，令n等于\[ gcd(a,b)/k=1 \]，就可以把左边的式子代入化简，最后变成求莫比乌斯函数的前缀和 ##

## 3.流程：对后面两个sigma进行整除分块，每次累加预处理的u函数和f数组(整除分块) ##

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

#include<bits/stdc++.h>
    using namespace std;
    #define N 50005
    #define ll long long
    ll pri[N],mu[N],sum[N],f[N],cnt=0,su[N];
    void suu()
    {
        mu[1]=1;
        int nn=N-5;
        for(int i=2;i<=nn;i++){
            if(!pri[i]) su[++cnt]=i,mu[i]=-1;
            for(int j=1;j<=cnt&&su[j]*i<=nn;j++){
                pri[su[j]*i]=1;
                if(i%su[j]) mu[su[j]*i]=-mu[i];
                else break;//mu=0
            }
        }
        for(int i=1;i<=nn;i++){
         //sqrt(n)的预处理 f[i]表示1~i中floor(p/i)的和 
            for(int l=1,r;l<=i;l=r+1){
         //枚举l和r 相当于整除分块里面的i和j 因为f会重复算 就直接算出重复的区间 用值来*上即可 
                 r=i/(i/l);
                 f[i]+=(r-l+1)*(i/l);
             }
         sum[i]=sum[i-1]+mu[i];//求一个莫比乌斯的函数前缀和 
        }
         
    }
    ll solve(int a,int b)
    {
        if(a>b) swap(a,b);
        ll ans=0;
        for(ll l=1,r;l<=a;l=r+1){
         //还要再一次整除分块 是后面那个枚举约数的式子 
            r=min(a/(a/l),b/(b/l));//一定要记得取min 因为r跳的是值更小的那一个!!!
            ans+=(sum[r]-sum[l-1])*f[a/l]*f[b/l];//推出来的式子 
        }
        return ans;
    }
    int main()
    {
        freopen("c.in","r",stdin);
        freopen("c.out","w",stdout);
        int T;
        suu();
        scanf("%d",&T);
        while(T--){
            int n,m;
            scanf("%d%d",&n,&m);
            printf("%lld\n",solve(n,m));
        }
    }
    /*
    2
    7 4
    5 6
    */

转载于:https://www.cnblogs.com/mowanying/p/11272966.html

[Link 1]: https://www.luogu.org/problem/P3327
[1604661-20190730211251598-1387348056.png]: /images/20211101/1ec7a9b7eecd43e5aaabfa91d58e2466.png
[Link 2]: https://www.cnblogs.com/yanghaokun/p/11070013.html
[1604661-20190730211800634-1140265610.png]: /images/20211101/ae0997e26425478ea57e64bb36a55111.png
[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20211101/9b55c1efcad64a0ebc81c3b67b38d027.png