hdu 1286:新しい友達を探す(数論、オラ関数)

5730 ワード
HDU
新しい友達を探す
Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)Total Submission(s): 7001    Accepted Submission(s): 3643
Problem Description
新年はもうすぐ着いて、“ブタの頭は協会を手伝います”は1つのパーティーをするつもりで、すでに既存の会員のN人を知っていて、会員を1からNまで番号をつけて、その中の会長の番号はN番で、会長と古い友达で、それではこの会員の番号はきっとNと1より大きい公約数があって、さもなくばすべて新しい友达で、今会長はいったい何人の新しい友达がいることを知りたいですか?プログラムを作って会長の計算を手伝ってください.
 
 
Input
1行目は、テストデータのグループ数CN(Case number,1 
 
Output
Nごとに、新しい友达の人数を出力し、CN行の出力を共有します.
 
 
Sample Input
2 25608 24027
 
 
Sample Output
7680 16016
 
 
Author
SmallBeer(CML)
 
 
Source
杭電ACM合宿チーム訓練試合(VII)
 
 
Recommend
lcy   |   We have carefully selected several similar problems for you:  
1215  
1406  
1787  
1211  
3792  
 
数論、オーラ関数.
題意はあなたに1つの数をあげて、この数と互いに質の数の数を求めることです.
これはオーラ関数の応用であり,オーラ関数の役割は1つの数とその相互質の数の個数を求めることである.
私たちの実験室のある品物のオーラ関数の原理を聞いて、自分で一度実現して、結果は穴の中に落ちたことを発見しました.さっそくテンプレートをセットしましょう.どうせ原理がわかりました.
関連知識:
　　 せきぶんかんすう    　　 オーラ関数
コード:
 1 #include <iostream>

 2 #include <cmath>

 3 using namespace std;  4 int Ealer(int x)  5 {  6     int i,res = x;  7     for(i=2;i<(int)sqrt(x*1.0)+1;i++)  8         if(x%i==0){  9             res = res / i * (i-1); 10             while(x%i==0) 11                 x/=i;    //  i     

12  } 13     if(x>1) res = res/x*(x-1); 14     return res; 15 } 16 int main() 17 { 18     int cn; 19     cin>>cn; 20     while(cn--){ 21         int n; 22         cin>>n; 23         cout<<Ealer(n)<<endl; 24  } 25     return 0; 26 }

 
Freecode : www.cnblogs.com/yym2013
初めてのnginxでオレオレ証明書https（2020/12/19）
hdu 2025:最大要素の検索(水題、順序検索)