BZOJ3994：利用莫比烏斯反演求約數(shù)個數(shù)和

解答此題需要利用約束個數(shù)函數(shù)的形式，將其與gcd聯(lián)系再一起，然后再反演，推導

很麻煩

1 #include<cstdio> 2 #include<algorithm> 3 using std::min; 4 const int maxn=50005; 5 int cnt; 6 long long ans=0; 7 bool vis[maxn]; 8 int mu[maxn],sum[maxn]; 9 long long prim[maxn],g[maxn]; 10 inline long long read() 11 { 12 long long x=0,f=1;char ch=getchar(); 13 while(ch<'0'||ch>'9') {if(ch=='-')f=-1;ch=getchar();} 14 while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} 15 return x*f; 16 } 17 void get_mu(int n) 18 { 19 mu[1]=1; 20 for(int i=2;i<=n;i++) 21 { 22 if(!vis[i]){prim[++cnt]=i;mu[i]=-1;} 23 for(int j=1;j<=cnt&&prim[j]*i<=n;j++) 24 { 25 vis[prim[j]*i]=1; 26 if(i%prim[j]==0) break; 27 else mu[i*prim[j]]=-mu[i]; 28 } 29 } 30 for(int i=1;i<=n;i++) sum[i]=sum[i-1]+mu[i]; 31 for(int i=1;i<=n;i++) 32 { 33 for(int l=1,r;l<=i;l=r+1) 34 { 35 r=(i/(i/l)); 36 g[i]+=(long long)(r-l+1)*(long long)(i/l); 37 } 38 } 39 } 40 int main() 41 { 42 int T,n,m,max_rep; 43 T=read(); 44 get_mu(50000); 45 while(T--) 46 { 47 ans=0; 48 n=read();m=read(); 49 max_rep=min(n,m); 50 for(int l=1,r;l<=max_rep;l=r+1) 51 { 52 r=min(n/(n/l),m/(m/l)); 53 ans+=(sum[r]-sum[l-1])*(long long)g[n/l]*(long long)g[m/l]; 54 } 55 printf("%lld\n",ans); 56 } 57 return 0; 58 }

?

轉載于:https://www.cnblogs.com/aininot260/p/9702622.html

創(chuàng)作挑戰(zhàn)賽新人創(chuàng)作獎勵來咯，堅持創(chuàng)作打卡瓜分現(xiàn)金大獎

總結

以上是生活随笔為你收集整理的数学：莫比乌斯反演-约数个数和的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內容還不錯，歡迎將生活随笔推薦給好友。