您當前位置：首頁 > php開源 > php教程 > [置頂] HDU 1286 歐拉函數。

[置頂] HDU 1286 歐拉函數。

來源：程序員人生發布時間：2015-01-05 08:07:00 閱讀次數：2448次

【科普】甚么是BestCoder？如何參加？

找新朋友

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 8077 Accepted Submission(s): 4250

Problem Description

新年快到了，“豬頭幫協會”準備弄1個集會，已知道現有會員N人，把會員從1到N編號，其中會長的號碼是N號，凡是和會長是老朋友的，那末該會員的號碼肯定和N有大于1的公約數，否則都是新朋友，現在會長想知道究竟有幾個新朋友？請你編程序幫會長計算出來。

Input

第1行是測試數據的組數CN（Case number，1<CN<10000），接著有CN行正整數N（1<n<32768），表示會員人數。

Output

對每個N，輸出1行新朋友的人數，這樣共有CN行輸出。

Sample Input

2 25608 24027

Sample Output

7680 16016

Author

SmallBeer(CML)

Source

杭電ACM集訓隊訓練賽（VII）

歐拉乃真神人不知道怎樣證明的。

其實題意就是這個：在數論，對正整數n，歐拉函數是少于或等于n的數中與n互質的數的數目。此函數以其首名研究者歐拉命名，它又稱為Euler's totient function、φ函數、歐拉商數等。例如φ(8)=4，由于1,3,5,7均和8互質。從歐拉函數引申出來在環論方面的事實和拉格朗日定理構成了歐拉定理的證明。

找出和m互質的。

上代碼吧。

#include<string.h> #include <stdio.h> int g[32770]; int ouler(int x) { int i,k=1; int m=x; for(i=2;i<=m;i++) { if(m%i==0) { k=k*(i⑴); while(m%i==0) { m=m/i; k*=i; } k/=i; } } return k; //以上是查資料寫出的，至于為何是這樣的由于證明實在看不懂，我不知道。 } int main() { int ncase,m; scanf("%d",&ncase); while(ncase--) { scanf("%d",&m); printf("%d ",ouler(m)); } return 0; }

生活不易，碼農辛苦
如果您覺得本網站對您的學習有所幫助,可以手機掃描二維碼進行捐贈
程序員人生

------分隔線----------------------------

上一篇 thinkphp小結

下一篇 C++應用程序的入口

分享到:

------分隔線----------------------------

為碼而活

積分：4237

15粉絲

7關注

欄目熱點

多多色-多人伦交性欧美在线观看-多人伦精品一区二区三区视频-多色视频-免费黄色视屏网站-免费黄色在线

[置頂] HDU 1286 歐拉函數。

[置頂] HDU 1286 歐拉函數。