P3327 [SDOI2015]约数个数和

缺乏、安全感 2021-12-23 13:59 212阅读 0赞

### 思路 ###

做这题先要知道一个性质，

\\\[ d\_\{ij\}=\\sum\_\{x|i\}\\sum\_\{y|j\}\[(x,y)=1\] \\\]

然后上莫比乌斯反演颓柿子就好了

\\\[ \\begin\{align\}&\\sum\_\{i=1\}^n\\sum\_\{j=1\}^m\\sum\_\{x|i\}\\sum\_\{y|j\}\[(x,y)=1\]\\\\=&\\sum\_\{i=1\}^n\\sum\_\{j=1\}^m\\sum\_\{x|i\}\\sum\_\{y|j\}\\sum\_\{d|(x,y)\}\\mu(d)\\\\=&\\sum\_\{i=1\}^n\\sum\_\{j=1\}^m\\sum\_d^\{min(n,m)\}\\mu(d)\\sum\_\{x=1\}^\{\\lfloor\\frac\{i\}\{d\}\\rfloor\}\\sum\_\{y=1\}^\{\\lfloor\\frac\{j\}\{d\}\\rfloor\}1\\\\=&\\sum\_d^\{min(n,m)\}\\mu(d)\\sum\_\{i=1\}^n\\sum\_\{x=1\}^\{\\lfloor\\frac\{i\}\{d\}\\rfloor\}\\sum\_\{j=1\}^m\\sum\_\{y=1\}^\{\\lfloor\\frac\{j\}\{d\}\\rfloor\}1\\\\=&\\sum\_d^\{min(n,m)\}\\mu(d)\\sum\_\{x=1\}^\{\\lfloor\\frac\{n\}\{d\}\\rfloor\}\\lfloor\\frac\{n\}\{xd\}\\rfloor\\sum\_\{y=1\}^\{\\lfloor\\frac\{m\}\{d\}\\rfloor\}\\lfloor\\frac\{m\}\{dy\}\\rfloor\\\\=&\\sum\_d^\{min(n,m)\}\\mu(d)\\sum\_\{x=1\}^\{\\lfloor\\frac\{n\}\{d\}\\rfloor\}\\lfloor\\frac\{\\lfloor \\frac\{n\}\{d\}\\rfloor\}\{x\}\\rfloor\\sum\_\{y=1\}^\{\\lfloor\\frac\{m\}\{d\}\\rfloor\}\\lfloor\\frac\{\\lfloor \\frac\{m\}\{d\} \\rfloor\}\{y\}\\rfloor\\end\{align\}\\\\ \\\]

后面的部分，预处理一个\\(\\sum\_\{i=1\}^n \\lfloor \\frac\{n\}\{i\} \\rfloor\\)就好了，前面上一个整除分块

### 代码 ###

#include <cstring> #include <cstdio> #include <algorithm> using namespace std; int isprime[50010],mu[50010],cnt,iprime[50010],n,m,t; long long sum[50010]; void prime(int n){ mu[1]=1; isprime[1]=true; for(int i=2;i<=n;i++){ if(!isprime[i]){ iprime[++cnt]=i; mu[i]=-1; } for(int j=1;j<=cnt&&iprime[j]*i<=n;j++){ isprime[i*iprime[j]]=true; mu[i*iprime[j]]=-mu[i]; if(i%iprime[j]==0){ mu[i*iprime[j]]=0; break; } } } for(int i=1;i<=n;i++) mu[i]+=mu[i-1]; } void pre(int n){ for(int i=1;i<=n;i++){ long long ans=0; for(int l=1,r;l<=i;l=r+1){ r=i/(i/l); ans=ans+1LL*(r-l+1)*(i/l); } sum[i]=ans; } } int main(){ scanf("%d",&t); prime(50000); pre(50000); // printf("ok\n"); while(t--){ scanf("%d %d",&n,&m); long long ans=0; for(int l=1,r;l<=min(n,m);l=r+1){ r=min(n/(n/l),m/(m/l)); // printf("l=%d\n",l); ans=ans+1LL*(mu[r]-mu[l-1])*sum[n/l]*sum[m/l]; } printf("%lld\n",ans); } return 0; }

转载于:https://www.cnblogs.com/dreagonm/p/10640668.html