也是一个反演。
第一次手动推出一个简单的式子，激动.jpg
原题意思是求：
$Ans=sumlimits_{i=1}^{n}sumlimits_{j=1}^{m}phi(gcd(i,j))$
随意化几步试试：
$Ans=sumlimits_{d=1}^{min(n,m)}sumlimits_{i=1}^{n}sumlimits_{j=1}^{m}phi(d)[gcd(i,j)==d]$
$Ans=sumlimits_{d=1}^{min(n,m)}sumlimits_{i=1}^{frac{n}{d}}sumlimits_{j=1}^{frac{m}{d}}phi(d*gcd(frac{i}{d},frac{j}{d}))[gcd(i,j)==1]$
提前$phi(d)$函数
$Ans=sumlimits_{d=1}^{min(n,m)}phi(d)sumlimits_{i=1}^{frac{n}{d}}sumlimits_{j=1}^{frac{m}{d}}[gcd(i,j)==1]$
后面就是bzoj1101的形式了，随便化。
然后就可以分块了。
$phi,mu$可以前缀和，剩下的分块就好。
1 #include<bits/stdc++.h> 2 #define N 10000010 3 using namespace std; 4 typedef long long ll; 5 int n,m,prime[N],cnt,vis[N]; 6 ll f[N]; 7 void calcpre(){ 8 f[1]=1;cnt=0;memset(vis,1,sizeof(vis)); 9 for(int i=2;i<=N;i++){ 10 if(vis[i]){prime[++cnt]=i;f[i]=i-2;} 11 for(int j=1;j<=cnt;j++){ 12 int t=i*prime[j];if(t>N)break; 13 vis[t]=0;int p=prime[j]; 14 if (i%p)f[t]=f[i]*f[p]; 15 else{ 16 f[t]=(i/p)%p?f[i/p]*(p-1)*(p-1):f[i]*p; 17 break; 18 } 19 } 20 } 21 for(int i=2;i<=N;i++)f[i]+=f[i-1]; 22 } 23 inline int read(){ 24 int f=1,x=0;char ch; 25 do{ch=getchar();if(ch=='-')f=-1;}while(ch<'0'||ch>'9'); 26 do{x=x*10+ch-'0';ch=getchar();}while(ch>='0'&&ch<='9'); 27 return f*x; 28 } 29 int main(){ 30 freopen("aimiliyausemagic.in","r",stdin); 31 freopen("aimiliyausemagic.out","w",stdout); 32 calcpre();int T=read(); 33 while(T--){ 34 n=read();m=read(); 35 if(n>m)swap(n,m);ll ans=0; 36 for(int i=1,j=1;i<=n;i=j+1){ 37 j=min(n/(n/i),m/(m/i)); 38 ans+=(f[j]-f[i-1])*(n/i)*(m/i); 39 } 40 printf("%lld ",ans); 41 } 42 return 0; 43 }