HDU 1286 找新朋友

题目地址：http://acm.hdu.edu.cn/showproblem.php?pid=1286

思路：用欧拉函数找与N互质数的数量

#include<iostream>#include<cstdio>using namespace std;const int N=32770;int prime[N],phi[N];bool a[N];void is_prime(){int i,j,k;k=0;for(i=2;i<N;i++){   if(!a[i])   {       prime[k++]=i;      phi[i]=i-1;   }   for(j=0;j<k&&i*prime[j]<N;j++)   {      a[prime[j]*i]=1;  if(i%prime[j])  phi[i*prime[j]]=phi[i]*(prime[j]-1);  else  {     phi[i*prime[j]]=phi[i]*prime[j]; break;  }   }}}int main(){    int T,n;is_prime();scanf("%d",&T);while(T--){scanf("%d",&n);  printf("%d\n",phi[n]);}   return 0;}