筛法。
首先使cnt[i]=sqr(n/i)，这样cnt[i]就表示gcd(x,y)大于等于i的数对的个数，然后倒序枚举减去gcd大于i的个数就可以得到ans[i]。最终得到ans[1]。
这个算法单次复杂度是O(n)的，和欧拉函数线性筛一样，不过更好写。
但是T=600，欧拉函数只需要计算一次，每次输出就可以了，所以在T很大的情况下还是欧拉函数更好。
反正水题。。。
#include<cstdio> #include<algorithm> #include<cstring> using namespace std; const int maxn = 50000 + 10; int ans[maxn],cnt[maxn]; int n; void solve() { memset(ans,0,sizeof(ans)); for(int i=1;i<=n;i++) cnt[i]=(n/i)*(n/i); for(int i=n;i>=1;i--) { ans[i]=cnt[i]; for(int j=i*2;j<=n;j+=i) ans[i]-=ans[j]; } printf("%d\n",ans[1]); } int main() { while(scanf("%d",&n)==1&&n) solve(); return 0; }
原文：http://www.cnblogs.com/invoid/p/5574890.html