數論入門筆記

---

目錄

• 數論入門筆記
• 一、 數論是什么
• 二、數論基礎
• • • 1. 歐幾里德算法（輾轉相除法）
    • 2. 有關素數的基礎算法
    • • 單個整數素性測試
      • • • 簡單素數篩
      • 多個整數素性測試
      • • 埃氏篩法（Eratosthenes篩法）
        • • 區間篩法
          • 歐拉篩法（線性篩法）
    • 3. 擴展歐幾里德算法
  • 三. 模運算
  • 四. 快速冪運算
  • • 反復平方法
• 五、計數與概率
• • 1. 楊輝三角與二項式
  • 2. 數論中的計數問題
  • 3. 離散概率初步

---

一、 數論是什么

數論主要研究整數的性質。需要關注的是一些特殊的數，如質數，素數，最大公約數，最小公倍數等等，以及相應的歐幾里得算法，和各種篩法，歐拉函數，積性函數等等等等。。。。。。。

---

二、數論基礎

1. 歐幾里德算法（輾轉相除法）

可以通過歐幾里得算法來算出兩個正整數a，b的最大公約數。
復雜度：$O(log(max(a,b))$
代碼如下（示例）：

int gcd(int a, int b){return b == 0? a : gcd(b,a%b);//b==0 是遞歸的邊界條件}

下面是該程序的運算過程：

也可以直接調用庫函數__gcd(a,b);

2. 有關素數的基礎算法

單個整數素性測試

簡單素數篩

素數只有：素數它本身和1。判斷一個數是否是素數只需檢查 2 ~ /$\sqrt{(}n)$內的整數是否存在有能整除這個數的數就能判斷這個數是不是素數。
復雜度：$O(\sqrt{(}n))$
代碼如下（示例）：

bool is_prime() {for(int i=2;i*i<=n;i++){if(n%i==0)return false;}return n!=1; }

多個整數素性測試

n內的素數的總數大概是$n/ln(n)$個

埃氏篩法（Eratosthenes篩法）

用于高效去對多個整數進行素數檢測（素數的個數<= $10^6$)
2 ~ n的數寫入數組，之后找到最小并且沒有被劃去的數，之后將在2 ~ n之間這個數的倍數劃去，以此枚舉n以內的素數。
復雜度：$O(nlog(log(n)))$
代碼如下（示例）：

#define MAX_N 1000010 int prime[MAX_N]; bool is_prime[MAX_N+1]; int sieve(int n) {int p=0;for(int i=0;i<=n;i++) is_prime[i]=true;is_prime[0]=is_prime[1]=false;for(int i=2;i<=n;i++){if(is_prime[i]){prime[p++]=i;for(int j=2*i;j<=n;j+=i)is_prime[j]=false;}}return p; }

區間篩法

在區間[a,b)上 （a<b<=$10^{12}$,b-a<=$10^6$)
用埃氏篩法算出[2,$\sqrt{(}b)$]的質數，同時劃去[a,b)中這個質數的倍數。
代碼如下（示例）：

#define MAX_L 1000010 #define MAX_SQRT_B 1000010 typedef long long int ll; bool is_prime[MAX_L]; bool is_prime_small[MAX_SQRT_B]; void segment_sieve(ll a,ll b){for(int i=0;(ll)i*i<b;i++)is_prime_small[i]=true;for(int i=0;i<b-a;i++)is_prime[i]=true;for(int i=2;(ll)i*i<b;i++){if(is_prime_small[i]){for(int j=2*i;(ll)j*j<b;j+=i){is_prime_small[j]=false;}for(ll j=i*max(2LL,(a+i-1)/i);j<b;j+=i)is_prime[j]=false;}} }

歐拉篩法（線性篩法）

埃氏篩法在篩選時有重復，如6它被素數2和素數3都篩過，像這樣的數有很多，而歐拉篩法不會。

int prime[maxn]; int is_prime[maxn]; void Prime(){mem(is_prime,0);mem(prime, 0);for (int i = 2;i <= maxn; i++) {if (!is_prime[i]) {prime[++prime[0]] = i; //紀錄素數， 這個prime[0] 相當于 cnt，用來計數}for (int j = 1; j <=prime[0] && i*prime[j] <= maxn; j++) {is_prime[i*prime[j]] = 1;if (i % prime[j] == 0) {break;}}} }

3. 擴展歐幾里德算法

裴蜀定理
若a，b是整數，且gcd(a,b)=g，那么對于任意的整數x，y，ax+by=m中的m一定是g的倍數。反之ax+by=m有解，m一定是g的倍數。
它的一個重要推論是：a,b互質的充要條件是存在整數x,y使ax+by=1。

擴展歐幾里德算法這個算法原理如下：
$gcd（a,b）=gcd(b,amodb);$
$gcd(a,b)=a{x}_1+b{y}_1(裴蜀定理)$
$即gcd（b,amodb）=b{x}_2+(amodb)y_2$
推導通解：
$a{x}_1+b{y}_1=a{x}_2+b{y}_2$
$即a{x}_1+a{x}_2=b{y}_1+b{y}_2$
$兩邊同除gcd(a,b),簡寫g$//如果g=0，意味a=0 or b=0
$(a/g)(x_1+x_2)=(b/g)(y_1+y_2),有因為互素，所以(x_1+x_2)一定是（b/g）的倍數，所以可的通解為（x_0+k(b/g),y_0+k(b/g)）$
推導算法：
$a{x}_1+b{y}_1=b{x}_2+(amodb)y_2$
$已知x_2,y_2,amodb=a?(a/b)?b,代入$
$a{x}_1+b{y}_1=b{x}_2+(a?(a/b)?b)y_2=$
$a{x}_1+b{y}_1=a{y}_2+b(x_2?(a/b)y_2)$
$x_1=y_2,y_1=(x_2?(a/b)y_2)$
$當b=0時ax+by=gcd(a,0)=a;?>x=1,y=0;$//臨界條件

//1. void gcd(int a,int b,int& d,int& x,int& y) {if(!b){d=a;x=1;y=0;}else {gcd(b,a%b,d,y,x);y-=x*(a/b);} } //2. int extgcd(int a,int b,int &x,int &y)//擴展歐幾里得算法 {int d=a;if(b!=0){d=extgcd(b,a%b,x,y);y-=(a/b)*x;}else{x=1;y=0;}return d; }

費馬小定理
如果p是一個質數，而整數a不是p的倍數，則有$a^{p?1}\equiv 1(modp）$。
逆元
類似倒數，$ax\equiv bmodm;ac\equiv 1modm$; c就是a的逆元; $ac\equiv 1modm等價ac=1+mk$ ac-mk=1,這就成了 擴展歐幾里德算法。

int mod_inverse(int a,int b) {int x, y;extgcd(a,m,x,y);return (m+x%m)%m; }

三. 模運算

同余定理：
a mod b=c 則(a+b*k) mod b=c (k!=0)
(a+b) mod n=[(a mode n)+(b mod n)] mod n
(a-b) mod n=[(a mode n)-(b mod n)+n] mod n
a b mod n=(a mod n)(b mod n) mod n
注意乘法時可能會溢出所以要用long long int來保存中間結果
代碼如下（示例）：

int mul_mod(int a,int b,int mod) {a%=mod;b%=mod;return (int)(a*1LL*b)%mod;}

四. 快速冪運算

反復平方法

$x^n=（(x^2{)}^2)...$。
復雜度：$O(log(n))$

代碼如下（示例）：

typedef long long int ll; ll mod_pow(ll x,ll n,ll mod) {ll res = 1;while(n>0){if(n&1) res=res * x % mod;//當n為奇數時x=x*x%mod;n>>=1;}return res; }

五、計數與概率

1. 楊輝三角與二項式

$C[i][j]=C[i?1][j?1]+C[i?1][j]$

2. 數論中的計數問題

n的正約數的個數：$(a1+1)(a2+1)..(an+1)$
歐拉篩法求1-n的k次方的約數個數之和

const int size=1e7+5; bool prime[size];//is素數 int p[size];//素數 int sigma[size];//因質數個數 int tot=0;//素數個數 int k;//素數k次方 void init() {sigma[1]=1;for(int i=2;i<size;i++) prime[i]=true;for(int i=2;i<size;i++){if(prime[i]) {p[tot++]=i;sigma[i]=k+1;}for(int j=0;j<tot&&p[j]*i<size;j++){prime[i*p[j]]=false;if(i%p[j]==0){sigma[i*p[j]]=sigma[i]*2-sigma[i/p[j]];// 相當于break;}else {sigma[i*p[j]]=sigma[i]*(k+1);// 相當于}}} }

算小于與n互素的整數個數用歐拉函數。
$\phi$函數的值:

$$\phi (x)=x(1?1/p(1))(1?1/p(2))(1?1/p(3))\dots ..(1?1/p(n))$$ 其中$p(1),p(2)\dots p(n)$為x的所有質因數;x是正整數; $\phi (1)=1$(唯一和1互質的數，且小于等于1)。注意：每種質因數只有一個。

3. 離散概率初步

條件概率：$P（B|A）=P(AB)/P(A)$
全概率公式：$$P（B）=P(A1)P(B|A1)+P(A2)P(B|A2)+..$$

總結

以上是生活随笔為你收集整理的数论入门笔记的全部內容，希望文章能夠幫你解決所遇到的問題。

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