题目：https://www.luogu.org/problemnew/show/P2158
根据题目看出，除了 (1,0) (0,1) (1,1) 以外，所以可以看见的钉子 (x , y) x和y是互质的。
所以！明明显现就是欧拉函数。
欧拉函数表示1到N中与N互质的数的个数。
可以只跑一半，乘2。
然后加上3。
所以关键找出2到N的每个数的欧拉函数。
代码如下。
#include<bits/stdc++.h> using namespace std; const int maxn=40001; int n; int phi[maxn]; inline void euler(){ for(int i=2;i<=n;i++) phi[i]=i; for(int i=2;i<=n;i++) if(phi[i]==i) for(int j=i;j<=n;j+=i) phi[j]=phi[j]/i*(i-1); } int main() { scanf("%d",&n); euler(); if(n==1) {cout<<0<<endl;return 0;} long long ans=3; for(int i=2;i<n;i++) ans+=2*phi[i]; printf("%lld\n",ans); return 0; }
原文：https://www.cnblogs.com/ChrisKKK/p/10871085.html