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

传送门

公式太长了……我就直接抄一下这位大佬好了……实在懒得打了

首先据说$d(ij)$有个性质$$d(ij)=\sum_{x|i}\sum_{y|j}[gcd(x,y)=1]$$

我们所求的答案为$$ans=\sum_{i=1}^{n}\sum_{j=1}^{m}d(ij)$$

$$ans=\sum_{i=1}^{n}\sum_{j=1}^{m}\sum_{x|i}\sum_{y|j}[gcd(x,y)=1]$$

考虑一下$gcd(x,y)=1$，我们可以考虑莫比乌斯函数的性质，那么即$\sum_{d\mid n}\mu(d)$与$[n=1]$的结果相同

则有$$ans=\sum_{i=1}^{n}\sum_{j=1}^{m}\sum_{x|i}\sum_{y|j}\sum_{d|gcd(x,y)}\mu(d)$$

然后我们由枚举$gcd(x,y)$的约数改为直接枚举$d$

$$ans=\sum_{i=1}^{n}\sum_{j=1}^{m}\sum_{x|i}\sum_{y|j}\sum_{d=1}^{min(n,m)}\mu(d)*[d|gcd(x,y)]$$

然后把$\mu(d)$提取出来

$$ans=\sum_{d=1}^{min(n,m)}\mu(d)\sum_{i=1}^{n}\sum_{j=1}^{m}\sum_{x|i}\sum_{y|j}[d|gcd(x,y)]$$

然后，我们把枚举$i,j$和约数改为直接枚举约数，然后每个约数都会对他所有的倍数产生贡献

$$ans=\sum_{d=1}^{min(n,m)}\mu(d)\sum_{x=1}^{n}\sum_{y=1}^{m}[d|gcd(x,y)]\lfloor\frac{n}{x}\rfloor\lfloor\frac{m}{y}\rfloor$$

然后我们把枚举$x,y$改为枚举$dx,dy$，那么就可以把$[d|gcd(x,y)]$这个条件给消掉

$$ans=\sum_{d=1}^{min(n,m)}\mu(d)\sum_{x=1}^{\lfloor\frac{n}{d}\rfloor}\sum_{y=1}^{{\lfloor\frac{m}{d}\rfloor}}\lfloor\frac{n}{dx}\rfloor\lfloor\frac{m}{dy}\rfloor$$

$$ans=\sum_{d=1}^{min(n,m)}\mu(d)(\sum_{x=1}^{\lfloor\frac{n}{d}\rfloor}\lfloor\frac{n}{dx}\rfloor)(\sum_{y=1}^{{\lfloor\frac{m}{d}\rfloor}}\lfloor\frac{m}{dy}\rfloor)$$

然后$\sum_{x=1}^{\lfloor\frac{n}{d}\rfloor}\lfloor\frac{n}{dx}\rfloor$和$\sum_{y=1}^{{\lfloor\frac{m}{d}\rfloor}}\lfloor\frac{m}{dy}\rfloor$的前缀和都可以预处理，直接上整除分块就可以了

 //minamoto

 #include<iostream>

 #include<cstdio>

 #define ll long long

 using namespace std;

 #define getc() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)

 char buf[<<],*p1=buf,*p2=buf;

 inline int read(){

     #define num ch-'0'

     char ch;bool flag=;int res;

     while(!isdigit(ch=getc()))

     (ch=='-')&&(flag=true);

     for(res=num;isdigit(ch=getc());res=res*+num);

     (flag)&&(res=-res);

     #undef num

     return res;

 }

 const int N=;

 int vis[N],p[N],mu[N],sum[N],m;

 ll g[N],ans;

 void init(int n){

     mu[]=;

     for(int i=;i<=n;++i){

         if(!vis[i]) p[++m]=i,mu[i]=-;

         for(int j=;j<=m&&p[j]*i<=n;++j){

             vis[i*p[j]]=;

             if(i%p[j]==) break;

             mu[i*p[j]]=-mu[i];

         }

     }

     for(int i=;i<=n;++i) sum[i]=sum[i-]+mu[i];

     for(int i=;i<=n;++i){

         ans=;

         for(int l=,r;l<=i;l=r+){

             r=(i/(i/l));

             ans+=1ll*(r-l+)*(i/l);

         }

         g[i]=ans;

     }

 }

 int main(){

 //    freopen("testdata.in","r",stdin);

     init();

     int n,m,T,lim;scanf("%d",&T);

     while(T--){

         scanf("%d%d",&n,&m);

         lim=min(n,m),ans=;

         for(int l=,r;l<=lim;l=r+){

             r=min(n/(n/l),m/(m/l));

             ans+=(sum[r]-sum[l-])*g[n/l]*g[m/l];

         }

         printf("%lld\n",ans);

     }

     return ;

 }

巴特西

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

最新文章

热门文章