裸的2D gcd。ans=(Σ(d<=n)phi[d]*(n/d)*(m/d))*2-n*m;

    

1 #include
     
       2 #include
      
        3 #include
       
         4 #include
        
          5 #define int long long 6 using namespace std; 7 int n,m; 8 int pr[100005],su[100005],cnt,phi[100005]; 9 void shai()10 {11     phi[1]=1;12     for(int i=2;i<=100000;i++)13     {14         if(!phi[i])su[++cnt]=i,pr[i]=i,phi[i]=i-1;15         for(int j=1;su[j]<=pr[i]&&su[j]*i<=100000&&j<=cnt;j++)16         {17               pr[su[j]*i]=su[j];18               if(su[j]==pr[i])phi[su[j]*i]=phi[i]*su[j];19               else phi[su[j]*i]=phi[i]*(su[j]-1);20         }21     }22 }23 signed main()24 {25    shai();26    scanf("%lld%lld",&n,&m);int ans=0;27    for(int i=1;i<=min(n,m);i++)ans+=phi[i]*(n/i)*(m/i);28    ans*=2;ans-=(n*m);29    printf("%lld\n",ans);30    return 0;31 }