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

歐拉函數

系統 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條評論
主站蜘蛛池模板: 亚洲qingse中文久久网 | 奇米第四狠狠777高清秒播 | 最新中文字幕在线 | 亚洲精品视频久久 | 亚洲人人草 | 国内精品小视频 | 国产牛牛| 日本黄页免费 | 日韩一区二区三区在线免费观看 | 成人a在线| 欧美线人一区二区三区 | 91aaa在线观看 | 黄色在线免费 | 九九热在线视频免费观看 | 四虎国产精品永久在线看 | 成人午夜精品久久久久久久小说 | www.色午夜.com| 老子影院午夜精品欧美视频 | 国产精品99在线观看 | 91精品国产福利在线观看性色 | 97成人资源 | 欧美日韩亚洲在线观看 | 国产成人在线视频免费观看 | 中文字幕av在线 | 久久精品国产精品亚洲毛片 | 全黄一级裸片视频免费区 | 亚洲成人在线视频播放 | 人人干人 | 手机看片日韩国产 | 成人在线视频一区 | 中文字幕在线观看亚洲 | 久久99久久99 | 日韩欧美黄色大片 | 被公侵犯肉体中文字幕一区二区 | 曰本女人一级毛片看一级毛 | 亚洲精品一二三四 | 2022久久国产精品免费热麻豆 | 女人用粗大自熨喷水在线视频 | 26uuu色噜噜欧美在线播放 | 久久综合一区二区 | 日日碰日日摸日日澡视频播放 |