亚洲免费在线-亚洲免费在线播放-亚洲免费在线观看-亚洲免费在线观看视频-亚洲免费在线看-亚洲免费在线视频

歐拉函數

系統 1757 0
?

歐拉函數的定義:E(k)=([1,n-1]中與n互質的整數個數).
???
???? 由于隨意正整數都能夠唯一表示成例如以下形式:
???????????????????? k=p1^a1*p2^a2*……*pi^ai;(即分解質因數形式)
??? 能夠推出:E(k)=(p1-1)(p2-1)……(pi-1)*(p1^(a1-1))(p2^(a2-1))……(pi^(ai-1))
?????????????? =k*(p1-1)(p2-1)……(pi-1)/(p1*p2*……pi);
?????????????? =k*(1-1/p1)*(1-1/p2)....(1-1/pk)
???? ps:在程序中利用歐拉函數例如以下性質,能夠高速求出歐拉函數的值(a為N的質因素)
若(N%a==0 && (N/a)%a==0) 則有:E(N)=E(N/a)*a;

若(N%a==0 && (N/a)%a!=0) 則有:E(N)=E(N/a)*(a-1);

http://hi.baidu.com/ldante/blog/item/996b0ea131a7a58f46106443.html

第一次寫歐拉函數的題,琢磨的半天,最后還是僅僅能依照最開始的想法寫......
歐拉函數PHI(n)表示的是比n小,而且與n互質的正整數的個數(包含1)。比方:
PHI(1) = 1; PHI(2) = 1; PHI(3) = 2; PHI(4) = 2; ... PHI(9) = 6; ...

要計算一個正整數n的歐拉函數的方法例如以下:
1. 將n表示成素數的乘積: n = p1 ^ k1 * p2 ^ k2 * ... * pn ^ kn(這里p1, p2, ..., pn是素數)
2. PHI(n) = (p1 ^ k1 - p1 ^ (k1 - 1)) * (p2 ^ k2 - p2 ^ (k2 - 1)) * ... *
(pn ^ kn - pn ^ (kn - 1))
????????????? = Mult { pi ^ ki - pi ^ (ki -1) }

證明步驟例如以下:
1. easy想到:當n為素數時,PHI(n) = n - 1。由于每一個比n小的正整數都和n互素。當n為素數p的k次方時,PHI(n) = p ^ k - p ^ (k - 1)。由于在1到n之間的正整數僅僅有p的倍數和n不互素,這種數有(p ^ k / p)個。
2. 假設m和n互素,即GCD(m, n) = 1,那么PHI(m * n) = PHI(m) * PHI(n)。用中國剩余定理能夠證明,證明的思路是建立這樣一種一一相應的關系(a, b) <-> x,當中正整數a小于m而且gcd(a, m) = 1,正整數b小于n而且gcd(b, n) = 1,正整數x小于m*n而且gcd(m*n, x) = 1。證明步驟例如以下:
??? 1)依據中國剩余定理,假設m和n互素,那么關于未知量x的方程組x % m = a, x % n = b(0 <= a < m, 0 <= b < n),當0 <= x < m * n時存在而且僅存在一個解。easy證明,假設兩個這種方程組有同樣的m, n可是a, b不同,那么他們的解x一定不同。
??? 2)首先用反正法證明:gcd(m, a) = 1且gcd(n, b) = 1是gcd(m*n, x) = 1的必要條件:如果gcd(a, m) = k > 1,由此可得:a = a' * k; m = m' * k => x = k' * m + a = k' * k * m' + k * a' = k * (k' * m' + a'); 所以gcd(x, m) = k > 1。同理可證,如果gcd(b, n) > 1, 那么gcd(x, n) > 1。所以x和m * n互素的必要條件是a和m互訴且b和n互素。
??? 3)接下來我們證明充分性:由x % m = a 能夠得到x = k * m + a;由歐幾里德算法求最大公約數的過程(就不證明了,呵呵,還得想)能夠知道gcd(x, m) = gcd(m, a) = 1;同理可得,假設gcd(n, b) = 1那么gcd(x, n) = 1。接下來非常easy得到:gcd(m*n, x) = 1。從而證明了充分性。
??? 4)上面三步的結論表明,數對(a, b)是能夠和x建立起一一相應的關系的,所以有多少個不同的(a, b),就有多少個不同的x。
3.將n分解成素數乘積后,顯然對于隨意的i, j(i != j)都滿足 pi ^ ki和pj ^ kj是互素的,于是能夠的到上面的公式。

跟據上面的公式,能夠得到關于歐拉函數的遞推關系:
如果素數p能整除n,那么
假設p還能整除n / p, PHI(n) = PHI(n / p) * p;
假設p不能整除n / p, PHI(n) = PHI(n / p) * (p - 1);

以下是兩種求歐拉函數的不同編程方法:

/*==================================================*\
| 遞推求歐拉函數phi(i)
\*==================================================*/
for (i = 1; i <= maxn; i++) phi[i] = i;
for (i = 2; i <= maxn; i += 2) phi[i] /= 2;
for (i = 3; i <= maxn; i += 2) if(phi[i] == i) {
for (j = i; j <= maxn; j += i)
phi[j] = phi[j] / i * (i - 1);


/*==================================================*\
| 單獨求歐拉函數phi(x)
\*==================================================*/
unsigned euler(unsigned x)
{// 就是公式
unsigned i, res=x;
for (i = 2; i < (int)sqrt(x * 1.0) + 1; i++)
if(x%i==0) {
res = res / i * (i - 1);
while (x % i == 0) x /= i; // 保證i一定是素數
}
if (x > 1) res = res / x * (x - 1);
return res;
}

歐拉函數


更多文章、技術交流、商務合作、聯系博主

微信掃碼或搜索:z360901061

微信掃一掃加我為好友

QQ號聯系: 360901061

您的支持是博主寫作最大的動力,如果您喜歡我的文章,感覺我的文章對您有幫助,請用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧,狠狠點擊下面給點支持吧,站長非常感激您!手機微信長按不能支付解決辦法:請將微信支付二維碼保存到相冊,切換到微信,然后點擊微信右上角掃一掃功能,選擇支付二維碼完成支付。

【本文對您有幫助就好】

您的支持是博主寫作最大的動力,如果您喜歡我的文章,感覺我的文章對您有幫助,請用微信掃描上面二維碼支持博主2元、5元、10元、自定義金額等您想捐的金額吧,站長會非常 感謝您的哦!!!

發表我的評論
最新評論 總共0條評論
主站蜘蛛池模板: 免费看a毛片 | 亚洲精品国产专区一区 | 亚洲精品成人网久久久久久 | 伊人久久精品一区二区三区 | 曰本女人一级毛片看一级毛 | 在线欧美日韩国产 | 在线免费毛片 | 人与禽交免费网站视频 | 免费播放一区二区三区 | 天天色色网 | 久久亚洲热 | 亚洲精品久久久久久久777 | 一级呦女专区毛片 | 亚洲一区二区三区久久精品 | 久久99热66这里只有精品一 | 青青影院在线观看 | 97在线公开视频 | 亚洲宗合| 国产亚洲综合久久 | 床上毛片| 美国一级毛片免费看成人 | 伊人色综合久久天天爱 | 一本大道香蕉高清久久 | 九色 91| 天天操天天射天天操 | 高清欧美日本视频免费观看 | 四虎免费看黄 | 久久国产精品视频 | 91最新视频在线观看 | 99r精品视频| 久久精品视频一区 | 有码在线 | 亚州中文字幕 | 亚洲最大成人在线 | 久久这里只有精品视频99 | 久久国产首页 | xxx中国bbbwww | 色婷婷综合久久久久中文一区二区 | 伊在人香蕉99久久 | 四虎影视永久地址www成人污 | 日本欧美一区二区三区在线 |