简单思路
模拟发现关于y=x对称 (0,1)(1,0)(1,1)三个点单独处理
对于2<=x<=n 1<=y<n 的范围内 发现斜率 xy之间互质的点可被看见
对于每一列来说 满足条件的点等于欧拉(n) n为该列列号
因此 代码思路为:
计算从2到n的每一列的欧拉函数值 累加
累加结果乘以二 再加上三个单独处理的点 就是所有满足条件的点的数量了
#include<iostream>
#include<algorithm>
using namespace std;
//求 x y小于等于n时 所有x y互质的情况数
//只需计算2<=x<=n 1<=y<n 的所有情况 乘以二再加三
//这些情况数 可以用欧拉函数求 3+2*∑N i=1欧拉(i)
//oula n=n除以所有质因数 乘上所有质因数-1
int oula(int n){
int res=n;
for(int i=2;i<=n;i++)
if(n%i==0){
res=res/i*(i-1);
while(n%i==0)n/=i;
}
if(n>1)res=res/n*(n-1);
return res;
}
int main(){
int c;
cin>>c;
for(int k=1;k<=c;k++){
int n;
cin>>n;
int res=3;
for(int i=2;i<=n;i++){
res=res+2*oula(i);
}
cout<<k<<" "<<n<<" "<<res<<endl;
}
}