### Idea

$$f(k)=\sum\limits_{i=1}^n\sum\limits_{j=1}^m[gcd(i,j)=k]$$

$$F(k)=\sum\limits_{k|d}f(d)(d<=\min(n,m))$$

$$f(k)=\sum\limits_{k|d}\mu(\lfloor\frac{d}{k}\rfloor)F(d)$$

\begin{aligned}f(k)=&\sum\limits_{x=1}^{\min(\frac{n}{k},\frac{m}{k})}\mu(x)F(xk) \\ =& \sum\limits_{x=1}^{\min(\frac{n}{k},\frac{m}{k})}\mu(x) \lfloor\frac{n}{xk}\rfloor\lfloor\frac{m}{xk}\rfloor\end{aligned}

### Code

#include <bits/stdc++.h>
#define maxn 50010
#define min(a,b) (a<b?a:b)
#define ll long long
int x=0;char ch=getchar();
while(!isdigit(ch)) ch=getchar();
while(isdigit(ch)) x=(x<<3)+(x<<1)+(ch-'0'),ch=getchar();
return x;
}
bool vis[maxn];
int mu[maxn],pri[maxn],top;
int sum[maxn];
void init(int n){
mu[1]=1;
for (int i=2;i<=n;++i){
if (!vis[i])pri[++top]=i,mu[i]=-1;
for (int j=1;j<=top&&i*pri[j]<=n;++j){
vis[i*pri[j]]=1;
if (i%pri[j]) mu[i*pri[j]]=-mu[i];
else break;
}
}
for (int i=1;i<=n;++i)
sum[i]=sum[i-1]+mu[i];
}
ll calc(int n,int m,int k){
if (n>m) std::swap(n,m);
ll res=0;
int d=n/k;
for (int l=1,r;l<=d;l=r+1){
r=min((n/k)/(n/l/k),(m/k)/(m/l/k));
res+=1ll*(sum[r]-sum[l-1])*(1ll*(n/l/k)*(m/l/k));
}
return res;
}
int main(){
}