題目鏈接 http://acm.hdu.edu.cn/showPRoblem.php?pid=1286
Problem Description 新年快到了，“豬頭幫協會”準備搞一個聚會，已經知道現有會員N人，把會員從1到N編號，其中會長的號碼是N號，凡是和會長是老朋友的，那么該會員的號碼肯定和N有大于1的公約數，否則都是新朋友，現在會長想知道究竟有幾個新朋友？請你編程序幫會長計算出來。
Input 第一行是測試數據的組數CN（Case number，1< CN<10000），接著有CN行正整數N（1 < n<32768），表示會員人數。
Output 對于每一個N，輸出一行新朋友的人數，這樣共有CN行輸出。
Sample Input 2 25608 24027
Sample Output 7680 16016
來一發水題
#include<stdio.h>#define MAX_N 32770int phi[MAX_N];void init(){ for(int i=1;i<MAX_N;i++) phi[i]=i; for(int i=2;i<MAX_N;i++) if(phi[i]==i) for(int j=i;j<MAX_N;j+=i) phi[j]=phi[j]/i*(i-1);}int main(){ init();int T; scanf("%d",&T); while(T--){ int n; scanf("%d",&n); printf("%d/n",phi[n]); } return 0;}新聞熱點
疑難解答
