1 #include
     
       2 #include
      
        3 #include
       
         4 #define M 40005 5 using namespace std; 6 int ans,n,phi[M],q[M],tot,f[M]; 7 int main() 8 { 9     scanf("%d",&n);10     phi[1]=1;11     for(int i=2;i
        
         n)22               break;23             f[q[j]*i]=1;24             if(i%q[j])25               phi[i*q[j]]=phi[i]*(q[j]-1);26             else27               phi[i*q[j]]=phi[i]*q[j];28           }29       }30     for(int i=1;i
        
       
      
     

由题目可知 就是求互质的点对数目，如果把它按对角线分开处理，与i互质的数为phi(i)，用线性筛求欧拉函数。