本文作者參加過清北學堂NOIP2017訓練營提高組精英班，筆記非常詳細。特分享給大家！基本數論相關筆記較多，為方便大家閱讀，我們預計會分為三到四篇文章介紹給大家。

基本數論（一）

這是一個很大的專題同時也很重要，所以我十分再十分仔細地寫這個筆記，所以有點慢大家別介意。廢話不多說進入正題！

一、數論（研究整數性質的東西）：

1.數論的分類（來自百度百科）：

初等數論、解析數論、代數數論、幾何數論、計算數論、超越數論、組合數論、算術代數數論。

2.數：

整數、自然數（大於等於0的整數）、正整數（大於0的整數）、負整數、非負整數、非正整數、非零整數、奇數 偶數。

3.Problem 3：

設N為奇數，a1,a2,…,aN為1,2,…,N的一個排列，求證：(a1-1)(a2-2)…(aN-N)≡0(mod 2)。

證明：因為a1,a2,…,aN為1,2,…,N的一個排列，所以a1+a2+…+aN=1+2+…+N，移項，得：(a1-1)+(a2-2)+…+(an-N)=0為偶數，所以(a1-1),(a2-2),…,(an-N)中必定有至少一項為偶數，所以(a1-1)(a2-2)…(an-N)為偶數,即：(a1-1)(a2-2)…(aN-N)≡0(mod 2)。

4.整除性：

設a,b∈Z，如果存在c∈Z並且a=bc，則稱b|a（b為a的因子，「|」表示「能整除」）

5.質數：

如果一個數，只有1和自身作為因子的數，叫做質數（素數）。

通論1：存在一個質數p，若p|ab，則p|a或者p|b。

通論2：若p|a或者(p,a)=1（p和a的最大公因子為1），則p|a2 可以推出 p|a。

通論3：用π(x)表示不超過x的質數的個數，可以證：limπ(x)lnx÷x=1，換種通俗說法就是：1~x的質數個數大約為x/lnx（證明時間複雜度時可以用）。

6.Problem 3.141：

求證：當n為合數時，2n-1為合數。

證明：因為n為合數，我們可以令n=ab，則2n-1=(2a-1)·(2n-a+2n-2a+2n-3a+…+2a+1)，原式得證。

還可以看出平方差公式是這個的一個特例。

7.質數的判定：

（1）一個很多人都在用的辦法（判斷一個較小的數是否為質數）：

bool prime(int x)//判斷質數 時間複雜度：O(sqrt(x))，最多1012~1014

{

if(x<2) return false;

for(int a=2;a*a<=x;a++)

{

if(x%a==0) return false;//不是質數

}

return true;//是質數

}

（2）運用費馬小定理：

p為一個素數且p不是a的倍數，則有：ap-1≡1(mod p)（不能從右邊推到左邊）

做法：多次選取a檢驗p是否滿足費馬小定理（說明p可能是質數，選的滿足條件的a越多，p為質數的可能性越大）。

時間複雜度為：O(klogp)，選取k個a，判斷的過程用掉logp，總的加起來為klogp。

特別地，這樣的演算法有缺陷，因為有Carmichael數的存在，可導致上述演算法給出一個錯誤的判斷，例如：561、1105、1729，這三個數滿足費馬小定理，但是它們都是合數！

這裡給出1~10000的Carmichael數：561、1105、1729、2465、2821、6601、8911。

（3）Miller-Rabin演算法（判斷一個很大的數是否為質數）：

由於Carmichael數的存在，並且Carmichael數是有無窮多個的，那怎麼辦？打表？肯定不行啊！所以就要加強這個演算法！

如果n為素數，取a<n，令n-1=d×2r，則要麼ad≡1(mod n)，要麼存在一個數i滿足：0≤i＜r，使得：ad×2^i≡-1(mod n)，「一個數mod n=-1」可以表示為：「一個數mod n=n-1」，同樣地也是不能從右邊推到左邊。

時間複雜度：O(klogn)

做法：多次選取a檢驗p是否滿足，則是質數的概率就大。（有個好消息：不存在Carmichael數這樣的特殊情況！）

例如：12=3*22

int a[5]={3,7,11,23,37}//這裡選了鍾神喜歡的5個質數來檢驗是否滿足條件，如果不夠保險的話還可以多加幾個

bool Miller_Rabin(int n)//從a[]中選出5個a

{

n-1=d*2^r;//用n-1來確定d、r

for(int j=1;j<=5;j++)//這裡用了5個小於n的質數a來檢驗，用質數是因為效果更好！

{

if(pow(a[j],d)%n!=1)//不滿足第一個條件，pow為快速冪函數，pow(a,b)計算a^b

{

for(int i=0;i<r;i++)

{

if(pow(a[j],d*2^i)%n==-1) return true;//第二個條件

}

return false;

}

}

}

（4）篩法（處理1~n區間內有哪些質數）：

基本做法：給出要篩數值的範圍sqrt(n)，找出 sqrt(n)以內的素數p1,p2,p3,…,pk。先用2去篩，即把2留下，把2的倍數剔除掉；再用下一個素數，也就是3篩，把3留下，把3的倍數剔除掉；接下去用下一個素數5篩，把5留下，把5的倍數剔除掉；這樣不斷重複下去……

①非線性篩法；

bool not_prime[1000000];//true表示不是質數，false表示是質數

not_prime[1]=true;//1不是質數

for(int a=2;a<=n;a++)

{

for(int b=a+a;b<=n;b+=a)

{

not_prime[b]=true;

}

}

時間複雜度：(1/1+1/2+1/3+1/4+…+1/n)*n=nlogn

下面給出了優化版篩法，時間複雜度為：nlog(logn)

演算法思路：如果當前這個數是合數，之前已經枚舉過比它小的因子，在枚舉這個小因子的時候，已經把這個合數的倍數覆蓋掉了，所以沒必要。

bool not_prime[1000000];//優化版非線性篩法

not_prime[1]=true;//1不是質數

for(int a=2;a<=n;a++)

{

if(!not_prime[a])//如果是質數，進入循環，是合數就不進入

{

for(int b=a+a;b<=n;b+=a)

{

not_prime[b]=true;

}

}

}

②線性篩法：

演算法思路：每個合數都由它最小的質因子篩掉（代碼第12行）。一個合數會被拆成幾個質因子相乘，利用最小的質因子就可以把這個合數篩掉了，避免了重複篩的過程。

int not_prime[1000000];

int prime[1000000];//質數表

int prime_count=0;//質數的個數

memset(not_prime,0,sizeof(not_prime));

not_prime[1]=true;//1不是質數

for(int i=2;i<=n;i++)

{

if(!not_prime[i]) prime[++prime_count]=i;//把i放入質數表prime[]中

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;

}

}

時間複雜度：是線性的，接近於O(n)。

8.最大公因數：

（1）歐幾裏得演算法（輾轉相除法）：

原理什麼的我就不說了，看代碼YY一下就知道啦（詳見人教版高中數學必修三）。

int gcd(int a,int b)//歐幾裏得演算法 時間複雜度：O(loga)

{

if(!b) return a;

else return gcd(b,a%b);

}

int gcd(int a,int b)//簡化版歐幾裏得演算法 時間複雜度：O(loga)

{

return b?gcd(b,a%b):a;//一行代碼就是爽

}

（2）擴展歐幾裏得演算法：

用來在已知的a、b中求解一組x、y，使得ax+by=gcd(a,b)成立（根據數論相關定理，這組解一定存在）

求解過程（引自P2O5 dalao的blog：http://p2oileen.xyz/index.php/2017/06/07/exgcd/）：

設a>b，則有當b=0時，gcd(a,b)=a，此時x=1，y=0。

當ab≠0時，設ax1+by1=gcd(a,b)，因為gcd(a,b)=gcd(b,a%b)，則一定有：bx2(a%b)y2=gcd(b,a%b)=gcd(a,b)=ax1+by1

所以將bx2+(a%b)y2=ax1+by1移項+整理可得：

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

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

這樣我們就可以通過x2,y2遞歸求解x1,y1辣！

在gcd不斷遞歸求解的過程中，總會有一個時刻b=0，所以遞歸是有終止條件的。

遞歸代碼如下：

int Ex_Gcd(int a,int b,int &x,int &y)

{

if(b==0)

{

x=1;

y=0;

return a;

}

int ans=Ex_Gcd(b,a%b,x,y);

int t=x;

x=y;

y=t-a/b*y;

return ans;//返回a、b的最大公約數

}

9.中國剩餘定理（求解一次同餘式組）：

原問題：有物不知其數，三三數之剩二，五五數之剩三，七七數之剩二，問物幾何？

簡單地來說：有一個數x≡a1(mod p1)，x≡a2(mod p2)，x≡a3(mod p3)，…，x≡ak(mod pk)，求解一個最小的x。

根據問題，我們可以得出好多好多好多的方程：

x=k1p1+a1；x=k2p2+a2；……

兩個方程為一組，解之：

k1p1+a1=k2p2+a2移項得：k1p1-k2p2=a2-a1；

在我們小學的時候，就接觸了一個這樣的解法，很簡單很實用，現在就來模擬一下！

大數翻倍法（一種求解最小公倍數的方法）：

舉個栗子：

如要求兩個數的最小公倍數，則將較大數翻倍，一直翻倍到是較小數的倍數時那麼這個數就是這兩個數的最小公倍數。

如：6和7

7×1=7,7×2=14,7×3=21,7×4=28,7×5=35,7×6=42

42是6的倍數，那麼42就是6和7的最小公倍數。

這個演算法的基本思想就是：找到一個最大的ans，然後不斷翻倍，使它能夠整除其他所有的p

我們假設p1<p2，有：

//大數翻倍法 時間複雜度：O(min(p1,p2))

int fanbei(int a1,int p1,int a2,int p2)//p1<p2

{

ans=a2;

while(ans%p1!=a1) ans=ans+p2;

return ans;

}

根據ans=a2+p1p2≡a2(mod p1)，計算得出時間複雜度為O(min(p1,p2))，也就是說加p1次一定會找到一個解！

10.逆元：

定義：如果gcd(a,m)=1且存在唯一的b使得a×b≡1(mod m)且1≤b＜m，則b為a在模m意義下的逆元，a、b互為逆元。

舉個栗子：令a=3，m=7，我們希望找到一個b滿足a×b≡1(mod m)且1≤b＜m，不難找到b=5。則5為3在模7意義下的逆元，3、5互為逆元。

逆元的作用：在模的意義下做除法，舉個栗子：計算(3×6÷3)mod7的結果，按照一般的順序可以算出原式=(18÷3)mod7=6mod7=6。我們利用模的性質，可以把原式變為：(((3×6)mod7)÷3)mod7=4÷3mod7。我們發現進行到這裡就無法計算了（模意義下不能做除法），這時候就要用到逆元，3的逆元為5，所以原式"4÷3mod7"變為"4×5mod7"，計算得6。

尋找逆元的方法：

①費馬小定理：ap-1≡1(mod p)，p為質數，求a的逆元（保證a和p互質）？

兩邊同除以a得：ap-2≡1/a(mod p)，也就是說，任意一個數a在模質數p意義下的逆元就是ap-2。

②歐拉定理：aφ(m)≡1適用於任何數m，但要保證gcd(a,m)=1，解法和費馬小定理相同，φ(m)的意義之後會講。

11.積性函數：

定義：如果對於gcd(n,m)=1，有f(nm)=f(n)f(m)，則稱f為積性函數，例如f(x)=1就是積性函數。

給出一些經典的積性函數：

①σ(n)=Σd|nd：n的所有因子之和

②τ(n)=Σd|n1：n的因子個數

③μ(n)莫比烏斯函數，稍後會講（詳見13點）

④φ(n)歐拉函數：1~n當中與n互質的數的個數，例如φ(6)=2，下面介紹用大約O(n2)的方法求1~n的所有數的φ(ai)：

假設一個數n，求φ(n)？因為n=P1k1·P2k2·…·Prkr → φ(n)=n·(P1-1)/P1·(P2-1)/P2·…·(Pr-1)/Pr。

舉兩個例子：

30=2*3*5，所以φ(30)=30*(1/2)*(2/3)*(4/5)=8。

160=25*5，所以φ(160)=160*(1/2)*(4/5)=64。

講了這麼多的函數，怎麼樣用到積性的性質呢？

積性的意義在於：可以在O(n)的時間複雜度內，求出1~n所有數的函數值。

如下的例子（運用在歐拉函數）：我們在O(n)的時間內求出1~n所有數的φ值

要用到線性篩（其他的函數也是差不多——線性篩中加上函數即可）！

memset(notprime,0,sizeof(notprime)),notprime[1]=true;//初始化

phi[1]=1;//賦初值，φ(1)=1

for(int i=2;i<=n;i++)

{

if(!notprime[i])//是質數

{

prime[++prime_count]=i;

phi[i]=i-1;//如果i是質數，顯然和i互質的數有i-1個

}

for(int j=1;j<=prime_count;++j)//求合數的φ

{

if(prime[j]*i>n)//考慮prime[j]*i這個合數

{

break;

}

not_prime[prime[j]*i]=true;

/*根據積性函數定義，有φ(prime[j]*i)=φ(prime[j])*φ(i)，要用積性函數的性質，必須滿足prime[j]和i互質*/

if(i%prime[j]!=0)//prime[j]和i互質

{

phi[prime[j]*i]=phi[prime[j]]*phi[i];//直接利用積性函數性質

}

else//i是prime[j]的倍數（不互質）

{

phi[prime[j]*i]=prime[j]*phi[i];

/*把prime[j]*i分成prime[j]段，每段長度為i，那麼每一段與i互質的數一樣多，根據性質：若a與b互質，那麼a+b與b互質，a+2b與b互質，所以在第一段和i互質的數加上i之後還和prime[j]互質，所以整個裡面就有prime[j]*phi[i]個數和它是互質的，所以phi[prime[j]*i]=prime[j]*phi[i]*/

}

if(i%prime[j]==0) break;

}

}

12.卷積（這個我是真的不懂）：

f*g=Σd|nf(d)g (n/d)

13.莫比烏斯：

（1）莫比烏斯函數：

含義（三種情況）：拆解一個數n=P1k1*P2k2*P3k3*…*Prkr

①若n=1,μ(n)=1 ②當k1=k2=k3=…kr=1時,μ(n)=(-1)r ③前面兩個條件都不滿足時,μ(n)=0。

意義：容斥原理必備，多有使用到的地方，希望考慮一下吧。

（2）莫比烏斯反演：

以下兩個條件等價：

①對於任意正整數n，f(n)=Σd|ng(d)

②對於任意正整數n，g(n)=Σd|nμ(d)f(n/d)

14.一些東西：

①Σd|nφ(d)=n：一個數的因子的φ加起來等於n。

②Σd|nμ(d)=[n=1]：如果n=1，則n的所有因子的μ值和為1，否則為0。

15.歐拉定理：

費馬小定理的推廣：aφ(m)≡1(mod m)。

補充一些同餘的性質：

①反身性：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)，c≡d(mod m)，則a±c≡b±d(mod m)

⑤同餘式相乘：若a≡b(mod m)，c≡d(mod m)，則ac≡bd(mod m)

（未完待續）

推薦閱讀：

相關文章