题目：bzoj 2005 

　　   洛谷 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
     
      #include
      
       #include
       
        #include
        
         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
     
      #include
      
       #include
       
        #include
        
         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;}