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;}