先扔结论：点(a,b)与(0,0)之间有的数量为gcd(a,b)-1(怎么证的？？留给出题人）
我们求ans为所有gcd之和，但是复杂度过大，达到了O(n*m)，会T
于是想到一个容斥的办法：设F[i]表示因数中有i的数对组数，然后通过容斥地减去i的所有倍数的F，来得出原本的答案
需要注意的是要开longlong
#include<bits/stdc++.h> #define ll long long using namespace std; ll F[100010],ans; int n,m; int main(){ scanf("%d%d",&n,&m); for(int i=1;i<=min(n,m);i++) F[i]=(ll)(n/i)*(m/i); for(int i=min(n,m);i>=1;i--) for(int j=i*2;j<=min(n,m);j+=i) F[i]-=F[j]; for(int i=1;i<=min(n,m);i++)ans+=(ll)F[i]*i; printf("%lld",ans*2-(ll)n*m); return 0; }
原文：https://www.cnblogs.com/heqingyu/p/10630692.html