题目：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+;
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=;i*g<=n;i++)f[g]-=f[i*g];
// ans+=2*tmp;
ans+=(g*-)*f[g];
}
printf("%lld\n",ans);
return ;
}
方法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+;
int n,m,p[maxn],phi[maxn],cnt;
ll ans;
void init()
{
phi[]=;//!
for(int i=;i<=n;i++)
{
if(!phi[i])p[++cnt]=i,phi[i]=i-;
for(int j=;j<=cnt&&i*p[j]<=n;j++)
{
phi[i*p[j]]=phi[i]*(p[j]-);
if(i%p[j]==)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=;g<=n;g++)
ans+=*(ll)phi[g]*(n/g)*(m/g);
ans-=(ll)n*m;
printf("%lld\n",ans);
return ;
}