BZOJ3994：[SDOI2015]约数个数和—

BZOJ3994：[SDOI2015]约数个数和——题解

阅读量：6541 次

发布时间：2019-06-24

本文共 2352 字，大约阅读时间需要 7 分钟。

参考：

（他的公式好像最后一点有些问题）

请先锻炼好抗打击能力再做这道题，可以看我的

我们有$d(ij)=\sum_{k|i}\sum_{l|j}[gcd(k,l)==1]$

（感性证明很简单，于是就不证了）

（这个是本题第一难的地方，~~信息数学竞赛~~）

$\sum_{i=1}^n\sum_{j=1}^md(ij)$

$=\sum_{i=1}^n\sum_{j=1}^m\sum_{k|i}\sum_{l|j}[gcd(k,l)=1]$

$=\sum_{k=1}^n\sum_{l=1}^m\lfloor\frac{n}{k}\rfloor\lfloor\frac{m}{l}\rfloor[gcd(k,l)=1]$（跳了步，希望大家看得懂）

$=$套路~~（实则是跳步）~~

$=\sum_{d=1}^{min(n,m)}\mu(d)\sum_{k=1}^{n}\sum_{l=1}^{m}\lfloor\frac{n}{k}\rfloor\lfloor\frac{m}{l}\rfloor[k|d][l|d]$

$=\sum_{d=1}^{min(n,m)}\mu(d)\sum_{k=1}^{\lfloor\frac{n}{d}\rfloor}\sum_{l=1}^{\lfloor\frac{m}{d}\rfloor}\lfloor\frac{n} {kd}\rfloor\lfloor\frac{m}{ld}\rfloor$

我们令$g(n)=\sum_{i=1}^n\lfloor\frac{n}{i}\rfloor$

我们的套路有$\sum_{i=1}^n\sum_{j=1}^n[i|j]=g(n)$

是的你没有看错这玩意就是约数函数的前缀和。

（如果你还没看出来的话，把两个sigma颠倒一下）

（这是本题第二难的地方，~~信息数学竞赛~~）

于是预处理约数函数的前缀和。

（用到了算数基本定理的推导和约数函数是积性函数的性质，可见https://blog.csdn.net/ControlBear/article/details/77527115

（emmm……就算你全推出来了，这个不会也白搭，~~信息数学竞赛~~）

（我为什么要去作死做~~信息数学竞赛~~题啊！）

#include
    
     #include
     
      #include
      
       #include
       
        using namespace std;typedef long long ll;const int N=5e4+5;inline int read(){int x;scanf("%d",&x);return x;}ll su[N],miu[N],d[N],c[N];int he[N];void init(int n){    int tot=0;    miu[1]=d[1]=c[1]=1;    for(int i=2;i<=n;i++){        if(!he[i]){            su[++tot]=i;            miu[i]=-1;            c[i]=1;d[i]=2;        }        for(int j=1;j<=tot;j++){            if(i*su[j]>n)break;            he[i*su[j]]=1;            if(i%su[j]==0){                miu[i*su[j]]=0;                d[i*su[j]]=d[i]/(c[i]+1)*(c[i]+2);                c[i*su[j]]=c[i]+1;                break;            }else{                miu[i*su[j]]=miu[i]*miu[su[j]];                d[i*su[j]]=d[i]*d[su[j]];                c[i*su[j]]=1;               }        }    }    for(int i=1;i<=n;i++){        miu[i]+=miu[i-1];        d[i]+=d[i-1];    }}int main(){    init(5e4);    int t=read();    while(t--){        ll n=read(),m=read();        ll ans=0;        for(ll i=1,j;i<=min(n,m);i=j+1){            j=min(n/(n/i),m/(m/i));            ans+=(miu[j]-miu[i-1])*d[n/i]*d[m/i];        }        printf("%lld\n",ans);    }    return 0;}