bzoj 2005

裸的2D gcd。ans=(Σ(d<=n)phi[d]*(n/d)*(m/d))*2-n*m;
 1 #include<iostream>
 2 #include<cstdio>
 3 #include<algorithm>
 4 #include<cstring>
 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
",ans);
30    return 0;
31 }