在第i行当且仅当gcd(i,j)=1 可以被看到
欧拉函数求和 没了
1 /* http://www.cnblogs.com/karl07/ */ 2 #include <cstdlib> 3 #include <cstdio> 4 #include <cstring> 5 #include <cmath> 6 #include <map> 7 #include <algorithm> 8 using namespace std; 9 10 const int N=40005; 11 int phi[N]; 12 int n,ans=0; 13 14 void Phi(){ 15 phi[1]=1; 16 for (int i=2;i<=n;i++){ 17 if (!phi[i]){ 18 for (int j=i;j<=n;j+=i){ 19 if (!phi[j]) phi[j]=j; 20 phi[j]=phi[j]/i*(i-1); 21 } 22 } 23 } 24 } 25 26 int main(){ 27 scanf("%d",&n); 28 Phi(); 29 for (int i=1;i<=n-1;i++){ 30 ans+=phi[i]; 31 } 32 printf("%d ",ans*2+1); 33 return 0; 34 }