这题就是求 $\sum_{i=1}^{n}\sum_{j=1}^{m}(gcd(i,j)*2-1)$
我们考虑枚举k使 gcd(i,j)=k
定义 g[k]表示以k为公约数的i,j有多少对,f[k]表示以k为最大公约数的i,j有多少对
首先我们想k是若干个数的公约数(非最大) 那么 g[k]=(n/k)*(m/k)
而以k为最大公约数的时候 要用g[k]减掉 f[2k],f[3k],f[4k]...于是 $f[k]=g[k]-\sum_{i=1}^{i*k<=min(n,m)}f[i*k]$
最后求一下和就好了
下面是代码
#include <cstdio> #include <algorithm> using namespace std; const int N=100010; typedef long long LL; LL f[N],n,m,mx,ans; int main(){ //freopen("2005.in","r",stdin);freopen("2005.out","w",stdout); scanf("%lld%lld",&n,&m);mx=min(n,m); for(int i=1;i<=mx;i++) f[i]=(n/i)*(m/i); for(int i=mx;i>=1;i--) for(int j=2;j*i<=mx;j++) f[i]-=f[j*i]; for(int i=1;i<=mx;i++) ans+=(i*2-1)*f[i]; printf("%lld",ans); return 0; }