http://www.lydsy.com/JudgeOnline/problem.php?id=2190 (题目链接)
题意
一个N*N的方阵，问右下角的人能看到几个人。
Solution
如果一个人(x,y)要被看到，那么当且仅当gcd(x,y)=1，否则的话，一定存在一个人(x/gcd(x,y),y/gcd(x,y))挡住了看向这个人的视线。
这样一来，求得就是1~N范围内的互质数对了，欧拉函数前缀和搞一下，*2+1即可。
细节
注意边界
代码
// bzoj2190
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<cstdio>
#include<cmath>
#define LL long long
#define inf 2147483640
#define Pi acos(-1.0)
#define free(a) freopen(a".in","r",stdin),freopen(a".out","w",stdout);
using namespace std; const int maxn=40010;
int phi[maxn],p[maxn],vis[maxn],n,tot; void calphi() {
phi[1]=1;
for (int i=2;i<=n;i++) {
if (!vis[i]) {p[++tot]=i;phi[i]=i-1;}
for (int j=1;j<=tot;j++) {
if (i*p[j]>n) break;
vis[i*p[j]]=1;
if (i%p[j]==0) {phi[i*p[j]]=phi[i]*p[j];break;}
else phi[i*p[j]]=phi[i]*(p[j]-1);
}
}
}
int main() {
scanf("%d",&n);
calphi();
int ans=0;
for (int i=1;i<n;i++) ans+=phi[i];
printf("%d",2*ans+1);
return 0;
}