hdu hdoj 1286 找新朋友.doc

问题描述 找新朋友 Time Limit: 2000/1000 MS (Java/Others)????Memory Limit: 65536/32768 K (Java/Others)Total Submission(s): 3101????Accepted Submission(s): 1527 Problem Description 新年快到了，“猪头帮协会”准备搞一个聚会，已经知道现有会员N人，把会员从1到N编号，其中会长的号码是N号，凡是和会长是老朋友的，那么该会员的号码肯定和N有大于1的公约数，否则都是新朋友，现在会长想知道究竟有几个新朋友？请你编程序帮会长计算出来。 ? Input 第一行是测试数据的组数CN（Case number，1CN10000），接着有CN行正整数N（1n32768），表示会员人数。 ? Output 对于每一个N，输出一行新朋友的人数，这样共有CN行输出。 ? Sample Input 2 25608 24027 ? Sample Output 7680 16016 ? Author SmallBeer(CML) ? Source 杭电ACM集训队训练赛（VII） ? Recommend lcy //欧拉公式 n=p1^a1*p2^a2*……*pm^am，pj是素数，则有φ(n)=n(1-1/p1)(1-1/p2)……(1-1/pm) #include cstdio #include cmath #include cstdlib #include cstring int eular(int n) { int ret=1,i; for (i=2;i*i=n;i++) { if (n%i==0) { n/=i,ret*=i-1; while (n%i==0) n/=i,ret*=i; } } if (n1) ret*=n-1; return ret; } int main() { int n ,a ; scanf(%d,n); while(n--) { scanf(%d,a); int res = eular(a); printf(%d\n,res); } return 0; } //代码来源 陈元杰 #include iostream #include string #include cstring #include vector #include cmath #include algorithm using namespace std; #define MAX 32768 int f[MAX+1]; void prime() { int i,j; for(i=2;i=MAX;++i) f[i] = 1; f[0] = f[1] = 0; int len = (int)sqrt(double(MAX)); for(i=2;i=len;++i) { if(!f[i])continue; for(j=i*i;j=MAX;j+=i) { f[j] = 0; } } } int main() { prime(); int n; int i,j; int T; scanf(%d,T); int cnt=1; int flag[32769]; while(T--) { memset(flag,0,sizeof(flag)); scanf(%d,n); if(f[n]) { coutn-1endl; continue; } int len=n/2; for(i = 2;i=len;++i) { if(!f[i] || fla