我又来存档了。
1
11
2016
11
2016
POJ 2478 Farey Sequence
http://poj.org/problem?id=2478
上次听叶队说欧拉函数前缀和有O(n2/3)的求法，看到这道题就去写了一下。
我们考虑S(n)表示有多少对(x,y)满足gcd(x,y)=1且x，y<=n，那么我们要求的1-n的欧拉函数和即为(S(n)-1)/2，因为gcd(1,1)=1所以需要+1
