這是一個數論系列：）

一、素數

×費馬小定理

Theorem：?設 p 是一個素數,a 是一個整數且不是 p 的倍數,那么

很遺憾,費馬小定理的逆定理是不成立的。對 a = 2,滿足的非素數 n 是存在的。

比如 n = 341 = 11 × 31

對于整數 a,稱滿足的合數為以 a 為底的偽素數。

經測試,
前 10 億的自然數中,同時以 2 和 3 為底的偽素數有 1272 個。
我們用費馬小定理驗證素數的話,出錯的概率大概只有 0.000025。

×Miller-Rabin

Theorem：.若 p 是素數,x 是一個正整數,且 ?那么。

Corollary：設待測數為 n,取一個比 n 小的正整數 a,設,若 n 是素數,則要么，要么存在一個 i,滿足 0 ≤ i < r 且?。

Solution：隨機選取 k 個小于待測整數 n 的正整數作為底 a,用上面那個推論的逆定理來測試。時間復雜度O(k?log?n)。

這種方法仍是有反例的,但是若選擇 2 和 3 為底,第一個反例就大到了 1373653。

Example:給出一個正整數n， 求不超過n的所有素數。

Solution：

1.枚舉1-n的所有數做素數測試， 時間復雜度是O（n log n）。

2.逐次枚舉 2 到 n,設當前枚舉到 x,那么對所有滿足把標記為非素數。時間復雜度 O(n log n)。

3.線性篩法：

memset(not_prime, 0, sizeof(not_prime));
not_prime[1] = true;
for (int i = 2; i <= n; ++i)
{if (!not_prime[i]) prime[++ prime_count] = i;for (int j = 1; j <= prime_count; ++j){if (prime[j] * i > n) break;not_prime[prime[j] * i] = true;if (i % prime[j] == 0) break;}
}

關鍵在倒數第3行,它保證了我們總是能夠找到每個數的最小的那個素因子。因為每個不小于1 的整數的最小素因子個數是 1,所以復雜度是 O(n)。

×唯一分解定理

Theorem:每個大于1的整數均可分解為有限個素數的乘積， 并且若不計因子在分解中的次序， 則這種分解式是唯一的。

二、GCD 和 LCM

×Definition（GCD，LCM）：略。

×Example： 給兩個正整數a， b， 求他們的最大公約數和最小公倍數。

×Solution：歐幾里得算法

int Gcd(int a, int b) 
{if (b == 0) return a;else return Gcd(b, a % b);
}

求 n 個不超過 m 的正整數的最大公約數的復雜度是 O(n + log m)。

×Example：?求不定方程?ax + by = m 的整數解。

×Theorem：ax+ by = m 有整數解當且僅當 (a, b)|m。

×Theorem：設 (x0 , y0 ) 是不定方程 ax + by = m 的一組解,?(a, b) = g,那么全部解為，其中t為所有整數。

×Solution（擴展歐幾里得算法）

int ExGcd(int a, int b, int &x, int &y) 
{if (b == 0) {x = 1, y = 0;return a;}else {int g = ExGcd(b, a % b, x, y);int t = x;x = y, y = t - a / b * x;return g;}
}

考慮從 bx + (a mod b)y = g 的 (x, y) 推導到 ax′ + by′ = g 的 (x′ , y′ )。

以NOIp2012提高組Day2Mod一題為例子：

#include <cstdio>
#include <cstring>
#include <cstdlib>
using namespace std;
int exgcd(int a, int b, int &x, int &y)
{if (b == 0){x = 1, y = 0;return a;}else{int g = exgcd(b, a % b, x, y);int t = x;x = y, y = t - a / b * x;return g;}
}int main()
{int a, b, x, y, d;scanf("%d%d", &a, &b);d = exgcd(a, b, x, y);if (d == 1) printf("%d\n", (x % b + b) % b);return 0;
}

×Example：求解一次同余方程組

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ??

×Solution：當mi兩兩互素時， 是經典的中國剩余定理， 請自行百度或Google。

×Solution：介紹一種基于“合并”思想的算法， 當mi不滿足兩兩互素時， 也同樣能夠工作

可以寫成

設 g = gcd（m1, m2）， 若b2 - b1 能被g整除，則可以繼續

用擴展歐幾里得算法算出，則兩個同余式可以合并為

×Definition（逆元）：設正整數模m， 對于任意正整數a滿足（a， m） = 1, 總存在惟一的b滿足?且?， 稱b為模m意義下a的逆元。其實，嚴格意義上講b屬于模m的一個縮系。

×Example：給出正整數a 和 m,保證 (a, m) = 1,求模 m 意義下 a 的逆元。

×Solution：根據定義用擴展歐幾里得解一個線性同余方程即可

注意到 a × b ≡ 1 (mod m) 可以認為是 ，所以當我們需要在模 m意義下除以 a 時,可以用乘上 b 來代替,這就是逆元的用途。

轉載于:https://www.cnblogs.com/joker0429/archive/2013/01/11/2909923.html

總結

以上是生活随笔為你收集整理的数论（一）——素数，GCD，LCM的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。