传送门 我们可以先考虑下三角矩阵，之后答案*2（上三角矩阵）+3右下角三个特殊点。 显然当坐标i，j(i,j)!=1满足gcd(i,j)=1时可以看得见。 所以我们用线性筛求欧拉函数，答案就是sigma(phi(i))*2+3(2<=i<=n).
#include<iostream>#include<cstdio>using namespace std;int n,ans,s,p;int main(){ scanf("%d",&n); ans=0; for (int i=2;i<n;i++){ s=i,p=i; for (int j=2;j*j<=p;j++) if (p%j==0){ s=s*(j-1)/j; while (p%j==0) p/=j; } if (p!=1) s=s*(p-1)/p; ans+=s; } PRintf("%d",ans*2+3);}//我懒得用线性筛了新闻热点
疑难解答
