题目要我们求的东西可以化为：
[sum_{i=1}^{n}sum_{j=1}^{m}2*gcd(i,j)-1
]
[-nm+2sum_{i=1}^{n}sum_{j=1}^{m}gcd(i,j)
]
(sum_{i=1}^{n}sum_{j=1}^{m}gcd(i,j)=)
[sum_{i=1}^{n}sum_{j=1}^{m}sum_{d|i,d|j}phi(d)
]
[sum_{d=1}^{n}sum_{i=1}^{lfloor frac{n}{d}
floor}sum_{j=1}^{lfloor frac{m}{d}
floor}phi(d)
]
[sum_{d=1}^{n}phi(d){lfloorfrac{n}{d}
floor}{lfloorfrac{m}{d}
floor}
]
所以原式为：
[-nm+2sum_{d=1}^{n}phi(d)lfloorfrac{n}{d}
floorlfloorfrac{m}{d}
floor
]
暴力枚举(d)计算即可
PS：这类带有(gcd(i,j))的式子用欧拉反演会比暴力枚举约数方便很多，比如说这题
代码：
#include<bits/stdc++.h>
using namespace std;
#define N 100007
#define ll long long
const int lim=1e5;
int pr[N],cnt,phi[N];
bool zhi[N];
void Init()
{
int i,j;
phi[1]=1;
for(i=2;i<=lim;i++)
{
if(!zhi[i])pr[++cnt]=i,phi[i]=i-1;
for(j=1;j<=cnt&&i*pr[j]<=lim;j++)
{
int p=pr[j],x=i*p;
zhi[x]=true;
if(i%p==0){phi[x]=phi[i]*p;break;}
phi[x]=phi[i]*(p-1);
}
}
}
int main()
{
int n,m,i;
ll ans=0;
Init();
scanf("%d%d",&n,&m);
ans=-1ll*n*m;
ll sum=0;
for(i=1;i<=n;i++)
sum+=1ll*phi[i]*(n/i)*(m/i);
ans+=2*sum;
printf("%lld
",ans);
return 0;
}