题目大意：给你n，求出一个n*n的人阵，你站在左下角，最多可以看到多少人
题解：转换一下，就成了求(n-1)*(n-1)中有多少个x，y轴互素的坐标，然后加上你上面的，你右边的，你右上方的三个人。
用欧拉筛筛出n及以内的质数，欧拉筛最大特点是它的时间复杂度是O(n)的（它还可以求出phi，即比它小的与它互质的数的个数）。它是先循环用第几个质数，再循环是它的几次。
设i是第一重循环，j是第二重循环，那么欧拉筛会在primelist[j]|i时会退出，这保证了每个合数会被它的一个质因数筛掉，用这个特性也可以求phi，如果i是质数，phi[i]=i-1；如果primelist[j]|i，phi[i*primelist[j]]=phi[i]*primelist[j]；不然，phi[i*primelist[j]]=phi[i]*phi[primelist[j]]。
最后，我们可以把2~n-1的phi加起来，再*2+3就是解。
C++ Code：
#include<cstdio>
#include<cstring>
const int maxn=40100;
using namespace std;
long long n,size,ans;
int phi[maxn],plist[maxn];
bool prime[maxn];
void getprime(){
prime[1]=false;
for (int i=2;i<n;i++){
if (prime[i]){
plist[++size]=i;
phi[i]=i-1;
}
for (int j=1;j<=size&&plist[j]*i<n;j++){
prime[i*plist[j]]=false;
if (i%plist[j]==0){
phi[i*plist[j]]=phi[i]*plist[j];
break;
}
phi[i*plist[j]]=phi[i]*phi[plist[j]];
}
}
}
int main(){
scanf("%d",&n);
memset(prime,1,sizeof(prime));
getprime();
for (int i=2;i<n;i++)ans+=phi[i];
printf("%lld\n",ans+1<<1|1);
}
原文：http://www.cnblogs.com/Memory-of-winter/p/7813075.html