歡迎訪問https://blog.csdn.net/lxt_Lucia～～

宇宙第一小仙女\(^o^)/～～萌量爆表求帶飛=≡Σ((( つ^o^)つ~ dalao們點個關注唄～～

?

數論入門～～ 本文主要整理了一下? 同余定理/費馬小定理/擴展歐幾里德算法/中國剩余定理? 各自的概念描述、結論證明和模板應用，需要的可以參考一下咯～

?

一.同余定理

?

1.描述：

? ? ? ?同余定理是數論中的重要概念。給定一個正整數m，如果兩個整數a和b滿足（a-b）能夠被m整除，即（a-b）/m得到一個整數，那么就稱整數a與b對模m同余，記作a≡b(mod m)。

?

2.符號：

? ? ? ?兩個整數a、b，若它們除以整數m所得的余數相等，則稱a與b對模m同余或a同余于b模m。記作a≡b(mod m)

?

3.定義：

? ? ? ?設m是大于1的正整數，a、b是整數，如果兩個整數同時除以一個整數得到的余數相同，即m|(a-b)，則稱a與b關于模m同余，記作a≡b(mod m)。顯然有如下事實：

• 若a≡0(mod m)，則m|a;
• a≡b(mod m)等價于a與b分別用m去除，余數相同。

?

4.證明?:

(1)? 充分性：?
若a和b用m相除留下相同的余數r，則?a=q1m+r,?b=q2m+r,q1和q2為某兩個整數，由此的a-b=(q1m+r)-(q2m-r)=m(q1-q2)，根據整除定義，我們有m|(a-b)，由同余式定義得出結論：a≡b(mod m)。

(2)? 必要性：?
若a和b用m相除留下相同的余數r，則?a=q1m+r,b=q2m+r,所以a-b=m(q1-q2)?故?m|(a-b)。

?

5.性質：

• 反身性：a≡a (mod m)

• 對稱性： 若a≡b(mod m)，則b≡a(mod m)

• 傳遞性： 若a≡b(mod m)，b≡c(mod m)，則a≡c(mod m)

• 同余式相加：若a≡b(mod m)，b≡c(mod m)，則a ± c≡b ± d(mod m)

• 同余式相乘：若a≡b(mod m)，b≡c(mod m)，則ac≡bd(mod m)

• 線性運算：如果a≡b(mod m)，c≡d(mod m)，那么a ± c≡b ± d(mod m)，且a * c≡b * d(mod m)

• 除法：若ac ≡ bc (mod m) c≠0 則 a≡ b (mod m/gcd(c,m)) 其中gcd(c,m)表示c,m的最大公約數。特殊地 ,gcd(c,m)=1 則a ≡ b (mod m)

• 冪運算：如果a ≡ b (mod m)，那么a^n ≡ b^n (mod m)

• 若a ≡ b (mod m)，n|m,則 a ≡ b (mod n)

• 若a ≡ b (mod mi) (i=1,2…n) 則 a ≡ b (mod [m1,m2,…mn]) 其中[m1,m2,…mn]表示m1,m2,…mn的最小公倍數

?

6.應用：

? ? (1)高精度對單精度取模

? ? ? ? ? ? ?一個高精度數對一個數取余，可以把高精度數看成各位數的權值與個位數乘積的和。如1234 = ((1 * 10 + 2) * 10 + 3) * 10 + 4，對這個數進行取余運算就是上面基本加和乘的應用。

#include<iostream> #include<string> using namespace std;int main(){string a;int b;cin >> a >> b;int len = a.length();int ans = 0;for(int i = 0; i < len; i++){ans = (ans * 10 + a[i] - '0') % b;}cout << ans << endl;return 0; }

?

? ? ?(2)快速冪取模

? ? ? ? ? ? ?將冪拆解為多個底數的平方次的積，如果指數為偶數，把指數除以2，并讓底數的平方次取余，如果指數為奇數，就把多出來的底數記錄下來，再執行偶數次的操作。

#include<iostream> using namespace std;int PowerMod(int a, int b, int c){int ans = 1;a = a % c;while(b > 0){if(b&1){ans *= (a % c);}b >>= 1;a = (a * a) % c;}ans %= c;return ans; }int main() {int a, b, c;cin >> a >> b >> c;cout << PowerMod(a, b, c) << endl;return 0; }

?

---

二.費馬小定理

?

1.費馬小定理：

假如p是質數，且gcd(a,p)=1，那么 a(p-1)≡1（mod p）。即：假如a是整數，p是質數，且a,p互質(即兩者只有一個公約數1)，那么a的(p-1)次方除以p的余數恒等于1。

?

2.同余證法：

? ? ? 任意取一個質數，比如13。考慮從1到12的一系列整數1,2,3,4,5,6,7,8,9,10,11,12，給這些數都乘上一個與13互質的數，比如3，得到3,6,9,12,15,18,21,24,27,30,33,36。對于模13來說，這些數同余于3,6,9,12,2,5,8,11,1,4,7,10。這些余數實際上就是原來的1,2,3,4,5,6,7,8,9,10,11,12，只是順序不同而已。
? ? ? ?把1,2,3,…,12統統乘起來，乘積就是12的階乘12！。把3,6,9,…,36也統統乘起來，并且提出公因子3，乘積就是312×12！。對于模13來說，這兩個乘積都同余于1,2,3,…,12系列，盡管順序不是一一對應，即312×12！≡12！mod 13。兩邊同時除以12！得312≡1 mod 13。如果用p代替13，用x代替3，就得到費馬小定理xp－1≡1 mod p。

以zoj3785為例：

It's Saturday today, what day is it after 1^1 + 2^2 + 3^3 + ... + N^N days??(1 <=?N?<= 1000000000).

對于

1^1 2^2 3^3 4^4 5^5 6^6 7^7 8^8 9^9 10^10 11^11 12^12 13^13 14^14 15^15 16^16 17^17 18^18 19^19 20^20 21^21 22^22 23^23 24^24 25^25 26^26 27^27 28^28 29^29 30^30 31^31 32^32 33^33 34^34 35^35 36^36 37^37 38^38 39^39 40^40 41^41 42^42 43^43 44^44 45^45 46^46 47^47 48^48 49^49

都對7取模后

1^1 2^2 3^3 4^4 5^5 6^6 0^7 1^8 2^9 3^10 4^11 5^12 6^13 0^14 1^15 2^16 3^17 4^18 5^19 6^20 0^21 1^22 2^23 3^24 4^25 5^26 6^27 0^28 1^29 2^30 3^31 4^32 5^33 6^34 0^35 1^36 2^37 3^38 4^39 5^40 6^41 0^42 1^43 2^44 3^45 4^46 5^47 6^48 0^49

根據費馬小定理x6≡1（mod 7）可得

1^1 2^2 3^3 4^4 5^5 6^6 0 1^2 2^3 3^4 4^5 5^6 6^1 0 1^3 2^4 3^5 4^6 5^1 6^2 0 1^4 2^5 3^6 4^1 5^2 6^3 0 1^5 2^6 3^1 4^2 5^3 6^4 0 1^6 2^1 3^2 4^3 5^4 6^5 0 1^1 2^2 3^3 4^4 5^5 6^6 0

每六行一個循環，循環節長度為42

#include<stdio.h> #include<algorithm> #include<iostream> #include<string.h> #include<stdlib.h> #include<queue> #include<vector> #include<math.h> #include<stack> using namespace std; const int MAX = 1000+10; const double eps = 1e-10; const double PI = acos(-1.0); long long n; int t; int s[50]; int main() {for(int i=1; i<=44; i++){int flag=i%7;int ans=1;for(int j=1; j<=i; j++)ans=(ans*flag)%7;s[i]=ans;}for(int i=1; i<=44; i++)s[i]+=s[i-1];scanf("%d", &t);long long ans;while(t--){scanf("%lld", &n);ans=(n/42%7*(s[42]%7)%7+s[n%42]%7)%7;ans = (ans+6)%7;if(ans==1)printf("Monday\n");else if(ans==2)printf("Tuesday\n");else if(ans==3)printf("Wednesday\n");else if(ans==4)printf("Thursday\n");else if(ans==5)printf("Friday\n");else if(ans==6)printf("Saturday\n");else printf("Sunday\n");}return 0; }

?

---

三.歐幾里德算法 and 擴展歐幾里德算法(gcd and exgcd)

?

(一) 歐幾里德算法 (gcd)

?

1.描述：

? ? ? ? 歐幾里德算法又稱輾轉相除法，用于計算兩個整數a,b的最大公約數。

?

2.基本算法：

? ? ? ?設a=qb+r，其中a，b，q，r都是整數，則gcd(a,b)=gcd(b,r)，即gcd(a,b)=gcd(b,a%b)。

?

3.證明：

? ? ? 方法一：

? ? ? a可以表示成a = kb + r，則r = a mod b

　　假設d是a,b的一個公約數，則有

　　d|a, d|b，而r = a - kb，因此d|r

　　因此d是(b,a mod b)的公約數

　　假設d 是(b,a mod b)的公約數，則

　　d | b , d |r ，但是a = kb +r

　　因此d也是(a,b)的公約數

　　因此(a,b)和(b,a mod b)的公約數是一樣的，其最大公約數也必然相等，得證

?

? ? 方法二：

? ??要證歐幾里德算法成立，即證: gcd(a,b)=gcd(b,r),其中 gcd是取最大公約數的意思，r=a mod b
??? 下面證 gcd（a，b）=gcd（b，r）
??? 設c是a，b的最大公約數，即c=gcd（a，b），則有 a=mc，b=nc，其中m，n為正整數，且m，n互為質數
??? 由 r= a mod b可知，r= a- qb 其中，q是正整數，
??? 則 r=a-qb=mc-qnc=（m-qn）c
??? b=nc,r=(m-qn)c，且n，（m-qn）互質（假設n，m-qn不互質，則n=xd, m-qn=yd 其中x,y,d都是正整數，且d>1
? ??則a=mc=(qx+y)dc, b=xdc,這時a,b 的最大公約數變成dc，與前提矛盾，所以n ，m-qn一定互質）
??? 則gcd（b,r）=c=gcd（a,b）
??? 得證。

?

4.算法的實現：

?(1)遞歸算法，代碼：

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

?(2)優化如下：

int gcd(int a,int b) {return b ? gcd(b,a%b) : a; }

?(3)用迭代形式：

int gcd(int a, int b) {while(b != 0){int r = b;b = a % b;a = r;}return a; }

?

(二) 擴展歐幾里德算法 (exgcd)

?

1.基本算法：

? ? ? ?對于不完全為 0 的非負整數 a，b，gcd（a，b）表示 a，b 的最大公約數，必然存在整數對 x，y ，使得 gcd（a，b）=ax+by。

2.證明：

? ? ? ?設 a>b。

　　(1) 當 b=0，gcd（a，b）=a。此時 x=1，y=0；

　　(2) ab!=0 時

　　設 ax1+by1=gcd(a,b);

　　bx2+(a mod b)y2=gcd(b,a mod b);

　　根據樸素的歐幾里德原理有 gcd(a,b)=gcd(b,a mod b);

　　則:ax1+by1=bx2+(a mod b)y2;

　　即:ax1+by1=bx2+(a-(a/b)*b)y2=ay2+bx2-(a/b)*by2;

　　根據恒等定理得：x1=y2; y1=x2-(a/b)*y2;

? ? ? 這樣我們就得到了求解 x1,y1 的方法：x1，y1 的值基于 x2，y2.

　 ?上面的思想是以遞歸定義的，因為 gcd 不斷的遞歸求解一定會有個時候 b=0，所以遞歸可以結束。

?

3.算法的實現：

?(1)遞歸代碼：

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

?(2)非遞歸代碼：

int exgcd(int m,int n,int &x,int &y) {int x1,y1,x0,y0;x0=1; y0=0;x1=0; y1=1;x=0; y=1;int r=m%n;int q=(m-r)/n;while(r){x=x0-q*x1; y=y0-q*y1;x0=x1; y0=y1;x1=x; y1=y;m=n; n=r; r=m%n;q=(m-r)/n;}return n; }

?

4.應用:

（1) 解決不定方程：

? ? ? ? 對于不定整數方程pa+qb=c，若 c mod Gcd(p, q)=0,則該方程存在整數解，否則不存在整數解。
上面已經列出找一個整數解的方法，在找到p * a+q * b = Gcd(p, q)的一組解p0,q0后，p * a+q * b = Gcd(p, q)的其他整數解滿足：
? ? ? ?p = p0 + b/Gcd(p, q) * t?
? ? ? q = q0 - a/Gcd(p, q) * t(其中t為任意整數)
至于pa+qb=c的整數解，只需將p * a+q * b = Gcd(p, q)的每個解乘上 c/Gcd(p, q) 即可。

在找到p * a+q * b = Gcd(a, b)的一組解p0,q0后，應該是得到p * a+q * b = c的一組解p1 = p0*(c/Gcd(a,b)),q1 = q0*(c/Gcd(a,b))，

? ? ? ?p * a+q * b = c的其他整數解滿足：

? ? ? p = p1 + b/Gcd(a, b) * t

? ? ? q = q1 - a/Gcd(a, b) * t(其中t為任意整數)

? ? ? p 、q就是p * a+q * b = c的所有整數解。

相關證明可參考：http://www.cnblogs.com/void/archive/2011/04/18/2020357.html

如，解不定方程ax+by=c代碼：

bool linear_equation(int a,int b,int c,int &x,int &y) {int d=exgcd(a,b,x,y);if(c%d)return false;int k=c/d;x*=k; y*=k; //求得的只是其中一組解return true; }

(2)求解模線性方程：

? ? 同余方程?ax≡b (mod n)對于未知數 x 有解，當且僅當 gcd(a,n) | b。且方程有解時，方程有 gcd(a,n) 個解。

? ? 求解方程 ax≡b (mod n)?相當于求解方程 ax+ ny= b, (x, y為整數)

? ? 設 d= gcd(a,n)，假如整數 x 和 y，滿足 d= ax+ ny(用擴展歐幾里德得出)。如果 d| b，則方程

? ? a* x0+ n* y0= d， 方程兩邊乘以 b/ d，(因為 d|b，所以能夠整除)，得到 a* x0* b/ d+ n* y0* b/ d= b。
? ? 所以 x= x0* b/ d，y= y0* b/ d 為 ax+ ny= b 的一個解，所以 x= x0* b/ d 為 ax= b (mod n ) 的解。

? ? ax≡b (mod n)的一個解為 x0= x* (b/ d ) mod n，且方程的 d 個解分別為 xi= (x0+ i* (n/ d ))mod n {i= 0... d-1}。

? ? 設ans=x*(b/d),s=n/d;

? ? 方程ax≡b (mod n)的最小整數解為：(ans%s+s)%s;

? ? 相關證明：

? ??證明方程有一解是: x0 = x'(b/d) mod n;
? ? 由?a*x0 = a*x'(b/d) (mod n)
?????????a*x0 = d (b/d) (mod n)?? (由于 ax' = d (mod n))
?????????????????= b (mod n)

? ??證明方程有d個解: xi = x0 + i*(n/d)? (mod n);
? ? 由 a*xi (mod n) = a * (x0 + i*(n/d)) (mod n)
?????????????????????????????= (a*x0+a*i*(n/d)) (mod n)
?????????????????????????????= a * x0 (mod n)?????????????(由于 d | a)
?????????????????????????????= b

? ? ?

? ? 首先看一個簡單的例子：

? ? 5x=4(mod3)

? ? 解得x = 2,5,8,11,14.......

? ? 由此可以發現一個規律，就是解的間隔是3.

? ? 那么這個解的間隔是怎么決定的呢？

? ? 如果可以設法找到第一個解，并且求出解之間的間隔，那么就可以求出模的線性方程的解集了.

? ? 我們設解之間的間隔為dx.

? ? 那么有

? ?a*x = b(mod n);

? ?a*(x+dx) = b(mod n);

? ?兩式相減，得到:

? ?a*dx(mod n)= 0;

? ?也就是說a*dx就是a的倍數，同時也是n的倍數，即a*dx是a 和 n的公倍數.為了求出dx,我們應該求出a 和 n的最小公倍數,此時對應的dx是最小的.

? ? 設a 和 n的最大公約數為d,那么a 和 n 的最小公倍數為(a*n)/d.

? ? 即a*dx = a*n/d;

? ? 所以dx = n/d.

? ? 因此解之間的間隔就求出來了.

? ? 代碼如下：

bool modular_linear_equation(int a,int b,int n) {int x,y,x0,i;int d=exgcd(a,n,x,y);if(b%d)return false;x0=x*(b/d)%n; //特解for(i=1;i<d;i++)printf("%d\n",(x0+i*(n/d))%n);return true; }

(3)求模的逆元:

? ? ? ?同余方程ax≡b (mod n)，如果 gcd(a,n)== 1，則方程只有唯一解。

? ? ? 在這種情況下，如果 b== 1，同余方程就是 ax=1 (mod n ),gcd(a,n)= 1。

? ? ? 這時稱求出的 x 為 a 的對模 n 乘法的逆元。

? ? ? 對于同余方程 ax= 1(mod n )， gcd(a,n)= 1 的求解就是求解方程

? ? ? ax+ ny= 1，x, y 為整數。這個可用擴展歐幾里德算法求出，原同余方程的唯一解就是用擴展歐幾里德算法得出的 x 。

?

---

四.中國剩余定理 ( 孫子定理 / CRT )

?

1.描述：

設正整數兩兩互素，則同余方程組

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

有整數解。并且在模下的解是唯一的，解為

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

其中，而為模的逆元。

?

2.代碼實現：

(1)互質：

//求M%A=a,M%B=b,...中的M，其中A,B,C...互質 int CRT(int a[],int m[],int n){ int M = 1; int ans = 0; for(int i=1; i<=n; i++) M *= m[i]; for(int i=1; i<=n; i++){ int x, y; int Mi = M / m[i]; ex_gcd(Mi, m[i], x, y); ans = (ans + Mi * x * a[i]) % M; } if(ans < 0) ans += M; return ans; }

(2)非互質：

一般的中國剩余定理要求mi兩兩互質，但是保證互質條件太苛刻了，若mi并不滿足兩兩互質時，就要采用兩兩合并的思想，假設要合并如下兩個方程?
x=a1+m1*x1?
x=a2+m2*x2

得到?
a1+m1*x1 = a2+m2*x2 → m1*x1+m2*x2 = a2-a1

再通過擴展歐幾里得算法解出x1的最小正整數解，代入?
x=a1+m1*x1

得到x后合并為一個方程的結果為?
y ≡ x(mod lcm(m1,m2))

這樣一直合并下去，最終可以求得同余方程組的解。

代碼：

bool merge(LL a1, LL m1, LL a2, LL m2, LL &a3, LL &m3) { LL d = gcd(m1, m2); LL c = a2 - a1; if(c % d) return false; c = (c % m2 + m2) % m2; m1 /= d; m2 /= d; c /= d; c *= Inv(m1, m2);//Inv為乘法逆元，數論常用內容——歐幾里得算法與擴展歐幾里得算法c %= m2; c *= m1 * d; c += a1; m3 = m1 * m2 * d; a3 = (c % m3 + m3) % m3; return true; } LL CRT(LL a[], LL m[], int n) { LL a1 = a[1]; LL m1 = m[1]; for(int i=2; i<=n; i++) { LL a2 = a[i]; LL m2 = m[i]; LL m3, a3; if(!merge(a1, m1, a2, m2, a3, m3)) return -1; a1 = a3; m1 = m3; } return (a1 % m1 + m1) % m1; }

?

3.例題：

(1) POJ 1006

題意：

人自出生起就有體力，情感和智力三個生理周期，分別為23，28和33天。一個周期內有一天為峰值，在這一天，人在對應的方面（體力，情感或智力）表現最好。通常這三個周期的峰值不會是同一天。現在給出三個日期，分別對應于體力，情感，智力出現峰值的日期。然后再給出一個起始日期，要求從這一天開始，算出最少再過多少天后三個峰值同時出現。

代碼：

#include <iostream> #include <string.h> #include <stdio.h>using namespace std;int a[4], m[4];void extend_Euclid(int a, int b, int &x, int &y) {if(b == 0){x = 1;y = 0;return;}extend_Euclid(b, a % b, x, y);int tmp = x;x = y;y = tmp - (a / b) * y; }int CRT(int a[],int m[],int n) {int M = 1;int ans = 0;for(int i=1; i<=n; i++)M *= m[i];for(int i=1; i<=n; i++){int x, y;int Mi = M / m[i];extend_Euclid(Mi, m[i], x, y);ans = (ans + Mi * x * a[i]) % M;}if(ans < 0) ans += M;return ans; }int main() {int p, e, i, d, t = 1;while(cin>>p>>e>>i>>d){if(p == -1 && e == -1 && i == -1 && d == -1)break;a[1] = p;a[2] = e;a[3] = i;m[1] = 23;m[2] = 28;m[3] = 33;int ans = CRT(a, m, 3);if(ans <= d)ans += 21252;cout<<"Case "<<t++<<": the next triple peak occurs in "<<ans - d<<" days."<<endl;}return 0; }

?

(2) POJ 2891

#include <iostream> #include <string.h> #include <stdio.h>using namespace std; typedef long long LL; const int N = 1005;LL a[N], m[N];LL gcd(LL a,LL b) {return b? gcd(b, a % b) : a; }void extend_Euclid(LL a, LL b, LL &x, LL &y) {if(b == 0){x = 1;y = 0;return;}extend_Euclid(b, a % b, x, y);LL tmp = x;x = y;y = tmp - (a / b) * y; }LL Inv(LL a, LL b) {LL d = gcd(a, b);if(d != 1) return -1;LL x, y;extend_Euclid(a, b, x, y);return (x % b + b) % b; }bool merge(LL a1, LL m1, LL a2, LL m2, LL &a3, LL &m3) {LL d = gcd(m1, m2);LL c = a2 - a1;if(c % d) return false;c = (c % m2 + m2) % m2;m1 /= d;m2 /= d;c /= d;c *= Inv(m1, m2);c %= m2;c *= m1 * d;c += a1;m3 = m1 * m2 * d;a3 = (c % m3 + m3) % m3;return true; }LL CRT(LL a[], LL m[], int n) {LL a1 = a[1];LL m1 = m[1];for(int i=2; i<=n; i++){LL a2 = a[i];LL m2 = m[i];LL m3, a3;if(!merge(a1, m1, a2, m2, a3, m3))return -1;a1 = a3;m1 = m3;}return (a1 % m1 + m1) % m1; }int main() {int n;while(scanf("%d",&n)!=EOF){for(int i=1; i<=n; i++)scanf("%I64d%I64d",&m[i], &a[i]);LL ans = CRT(a, m, n);printf("%I64d\n",ans);}return 0; }

?

(3) HDU 1573

分析：

? ? ? ??這個題由于數據范圍小，那么直接可以通過枚舉在這個數的最小公倍數范圍內的所有數，找到最小的正整數解，然后后面的所有解都可以通過這個得到。

代碼：

#include <iostream> #include <string.h> #include <stdio.h>using namespace std; const int N = 25;int a[N], b[N];int gcd(int a, int b) {return b ? gcd(b, a % b) : a; }int main() {int T;cin>>T;while(T--){int n, m;cin>>n>>m;for(int i=0; i<m; i++)cin>>a[i];for(int i=0; i<m; i++)cin>>b[i];int lcm = 1;for(int i=0; i<m; i++)lcm = lcm / gcd(lcm, a[i]) * a[i];bool f = 1;for(int i=1; i<=lcm&&i<=n; i++){f = 1;for(int j=0; j<m; j++){if(i % a[j] != b[j])f = 0;}if(f){printf("%d\n",(n - i) / lcm + 1);break;}}if(f == 0)printf("0\n");}return 0; }

?

參考資料：

https://blog.csdn.net/zcy_2016/article/details/55054146

https://blog.csdn.net/acdreamers/article/details/8050018

https://blog.csdn.net/tick_tock97/article/details/71313058

https://blog.csdn.net/qq_36345036/article/details/77407069

https://blog.csdn.net/QQ1353217816/article/details/79706975

http://www.cnblogs.com/frog112111/archive/2012/08/19/2646012.html

?

總結

以上是生活随笔為你收集整理的数论入门基础（同余定理/费马小定理/扩展欧几里德算法/中国剩余定理）～的全部內容，希望文章能夠幫你解決所遇到的問題。

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