题链：
http://www.lydsy.com/JudgeOnline/problem.php?id=2005
题解：
一个带有容斥思想的递推。
%%%
首先，对于一个点 (x,y) 在路径 (0,0)->(x,y)上，经过的点数为 GCD(x,y)-1
所以改点的贡献为 2*GCD(x,y)-1
N M
那么，ANS = ∑ ∑(2*GCD(i,j)-1)
i=1 j=1
显然超时。
考虑到 GCD<=100000，
那么是否可以求出 f[i] 表示 GCD==i的点对 (x,y)有多少个。
然后用f[i]去得出答案 (ans+=f[i]*(2*i-1))?
接下来就是神奇的递推了。
f[i]=(N/i)*(M/i) - f[i*k] (i*k<=min(N,M))
上式中 (N/i)*(M/i) 求得的是 有i这个公约数的点对(x,y)的个数
因为这些点对的最大公约数GCD可能为 i,2i,3i......
所以减掉f[2i],f[3i],f[4i]......就得到了f[i].
代码:
#include<cstdio>
#include<cstring>
#include<iostream>
#define ll long long
using namespace std;
ll f[100005];
ll N,M,K,ans;
int main()
{
freopen("energy.in","r",stdin);
freopen("energy.out","w",stdout);
cin>>N>>M; K=min(N,M);
for(int i=K;i>=1;i--){
f[i]=(N/i)*(M/i);
for(int j=2;i*j<=K;j++)
f[i]-=f[i*j];
ans+=f[i]*(2*i-1);
}
printf("%lld",ans);
return 0;
}
2.Möbius inversion formula
#include<cstdio>
#include<cstring>
#include<iostream>
#define MAXN 100500
using namespace std;
int mu[MAXN],pmu[MAXN];
void Sieve(){
static bool np[MAXN];
static int prime[MAXN],pnt;
mu[1]=pmu[1]=1;
for(int i=2;i<=100000;i++){
if(!np[i]) prime[++pnt]=i,mu[i]=-1;
for(int j=1;j<=pnt&&i<=100000/prime[j];j++){
np[i*prime[j]]=1;
if(i%prime[j]) mu[i*prime[j]]=-mu[i];
else break;
}
pmu[i]=pmu[i-1]+mu[i];
}
}
long long f(int n,int m){
long long ret=0; int mini=min(n,m);
for(int i=1,last;i<=mini;i=last+1){
last=min(n/(n/i),m/(m/i));
ret+=1ll*(pmu[last]-pmu[i-1])*(n/i)*(m/i);
}
return ret;
}
int main(){
Sieve();
int n,m,mini; long long ans=0;
scanf("%d%d",&n,&m); mini=min(n,m);
for(int g=1;g<=mini;g++)
ans+=(2*g-1)*f(n/g,m/g);
printf("%lld\n",ans);
return 0;
}