题目: bzoj 2005 https://www.lydsy.com/JudgeOnline/problem.php?id=2005
洛谷 P1447 https://www.luogu.org/problemnew/show/P1447
首先, 题意就是求 (1 <= i <= n) (1 <= j <= m) [ 2 * gcd(i,j) -1 ];
方法 1: 容斥原理
枚举每个数作为 gcd 被算了几次;
对于 d , 算的次数 f[d] 就是 n/d 和 m/d 中互质的数的对数;
所有数对的个数是 (n/d) * (m/d), 减去其中 gcd 是 2,3...... 的数对个数, 这里就可以用到之前算出来的答案;
比如要减去这之中 gcd 是 2 的数对, 那么减去 f[d/2] 即可, 而且因为定义原因不会重复减;
然后 *2 -1 即可.
代码如下:
- #include<iostream>
- #include<cstdio>
- #include<cstring>
- #include<algorithm>
- using namespace std;
- typedef long long ll;
- int const maxn=1e5+5;
- int n,m;
- ll f[maxn],ans;
- int main()
- {
- scanf("%d%d",&n,&m);
- if(n>m)swap(n,m);
- for(int g=n;g;g--)
- {
- f[g]=(ll)(n/g)*(m/g);//(ll) // 加括号! 因为要下取整
- for(int i=2;i*g<=n;i++)f[g]-=f[i*g];
- // ans+=2*tmp;
- ans+=(g*2-1)*f[g];
- }
- printf("%lld\n",ans);
- return 0;
- }
方法 2: 莫比乌斯反演
原式 (1 <= i <= n) (1 <= j <= m) [ 2 * gcd(i,j) - 1 ] ( n = min(m,n) )
由于 n = ( d|n ) φ(d) (感性理解: 约分......)
所以原式变成 (1 <= i <= n) (1 <= j <= m) [ 2 * ( d|i , d|j ) φ(d) - 1]
把 d 提前,-1 提出去 ( 1 <= d <= n ) [ 2 * φ(d) * (1 <= i <= n|d ) (1 <= j <= m|d ) 1 ] - n*m
也就是 2 * ( 1 <= d <= n ) [ φ(d) * (n/d) * (m/d) ] - n*m
注意 φ(1) = 1!
代码如下:
- #include<iostream>
- #include<cstdio>
- #include<cstring>
- #include<algorithm>
- using namespace std;
- typedef long long ll;
- int const maxn=1e5+5;
- int n,m,p[maxn],phi[maxn],cnt;
- ll ans;
- void init()
- {
- phi[1]=1;//!
- for(int i=2;i<=n;i++)
- {
- if(!phi[i])p[++cnt]=i,phi[i]=i-1;
- for(int j=1;j<=cnt&&i*p[j]<=n;j++)
- {
- phi[i*p[j]]=phi[i]*(p[j]-1);
- if(i%p[j]==0)phi[i*p[j]]=phi[i]*p[j];
- }
- }
- }
- int main()
- {
- scanf("%d%d",&n,&m);
- if(n>m)swap(n,m);
- init();
- for(int g=1;g<=n;g++)
- ans+=2*(ll)phi[g]*(n/g)*(m/g);
- ans-=(ll)n*m;
- printf("%lld\n",ans);
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2706005.html