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
Code:
#include <iostream>
using namespace std;
int Euler(int x)// 求 歐拉函數值 其實就是通式的應用
{
int i,res = x;
for(i = 2;i*i<=x;i++) //
{
if(x%i==0)
res = res/i*(i-1);
while(x%i==0) //保證周遊的一定是質因子
x/=i;
}
if(x>1)
res = res / x*(x-1);// x 若為1,則所有質因子全部周遊,不為1 則表示最後一個質因子殘餘,繼續res / x*(x-1)
return res;
}
int main()
{
int t,n;
cin>>t;
while(t--)
{
cin>>n;
cout<<Euler(n)<<endl;
}
return 0;
}