当$(x,y)$能被看到时，$gcd(x,y)=1$，
所以可以求$\sum_{i=0}^n\sum_{j=0}^n[gcd(x,y)=1]$
或者用欧拉函数
代码 #include<bits/stdc++.h>#define RG register#define clear(x, y) memset(x, y, sizeof(x));using namespace std;template<typename T>inline T read(){T data=0, w=1;char ch=getchar();while(ch!='-'&&(ch<'0'||ch>'9')) ch=getchar();if(ch=='-') w=-1, ch=getchar();while(ch>='0'&&ch<='9') data=(data<<3)+(data<<1)+(ch^48), ch=getchar();return data*w;}const int maxn(40010);int phi[maxn], prime[maxn], cnt;bool is_prime[maxn];int getphi(int n){for(RG int i=2;i<=n;i++){if(!is_prime[i]){prime[++cnt]=i;phi[i]=i-1;}for(RG int j=1;j<=cnt;j++){if(prime[j]*i>n) break;is_prime[prime[j]*i]=true;if(!(i%prime[j])) {phi[i*prime[j]]=phi[i]*prime[j];break;}else phi[i*prime[j]]=phi[i]*(prime[j]-1);}}}int n, ans;int main(){n=read<int>();getphi(n);if(n==1) return printf("0\n")&0;for(RG int i=3;i<=n;i++) ans+=phi[i-1];printf("%d\n", (ans<<1)+3);return 0;}转载于:https://www.cnblogs.com/cj-xxz/p/10185834.html
