數論 \(1\)

\(1.\) 質數

定義就不說了吧。

性質 \(\&\) 定理

• 質數 \(p\) 有且僅有兩個質因子 \(1\) 和 \(p\) 。

• 質數有無窮個。

• \([1,\, n]\) 中的質數個數約為 \(\dfrac{n}{\ln n}\) (此結論可用來大致估算某些數論題的資料範圍)。

• 任何一個大於 \(1\) 的整數 \(N\) 都可以分解成 \(N = {\large \prod}\limits_{i = 1}^k \, p_i^{\alpha_i} \ (\forall i ,\, p_i\in \mathbb P ,\, a_i \in \mathbb{N^*})\) 的形式，如果不計各個質因數的順序，那麼這種分解是惟一的。

篩質數——線性篩法

線性篩法，顧名思義，可以篩出 \([1,\, n]\) 內的所有質數，時間複雜度為 \(\mathcal O (n)\) 。

int primes[N], cnt;
// primes存放所有的質數，cnt是質數的數量
int st[N];
// st[i]記錄每個數是否是質數

void init(int n){
    for(int i = 2; i <= n; ++i){
        if(!st[i]) primes[cnt++] = i;
        for(int j = 0; primes[j] * i <= n && j < cnt; ++j){
            st[primes[j] * i] = 1;
            if(i % primes[j] == 0) break;
        }
    }
}

\(2.\) 約數

定義還是就不說了吧。~~

性質 \(\&\) 定理

• 對於任何一個大於 \(1\) 的整數 \(N\)，如果將其分解質因數為 \(N = {\large \prod}\limits_{i = 1}^k \, p_i^{\alpha_i} \ (\forall i ,\, p_i\in \mathbb P ,\, a_i \in \mathbb{N^*})\) 的形式，那麼 \(N\) 的正約數個數為 \({\large \prod}\limits_{i = 1}^k \, (\alpha_i + 1)\) ， \(N\) 的所有正約數的和為 \({\large \prod}\limits_{i = 1}^k \left({\large \sum}\limits_{j = 0}^{\alpha_i} \, p_i^j\right)\) 。
• \(2^{31}\) 內約數個數最多的數有 \(1600\) 個約數；\(2^{63}\) 內約數個數最多的數有 \(138240\) 個約數。

求約數個數

對於要重複計算多次的，先篩出質數，程式碼效率會有所提高。

int get_divisors(int x){
	int res = 1, s;
	for(int i = 0; primes[i] < x / primes[i]; ++i){
		int p = primes[i];
		s = 0;
		while(x % p == 0){
			++s;
			x /= p;
		}
		res *= s + 1;
	}
	if(x > 1) res *= 2;
    // 這裡一定記得判斷是否有還沒除盡的質因子
	
	return res;
}

\(3.\) 尤拉函數 \(\varphi\)

定義

\(\varphi(n)\) 表示小於等於 \(n\) 的正整數中與 \(n\) 互質的數的個數。

計算方法

對於任何一個大於 \(1\) 的整數 \(N\)，如果將其分解質因數為 \(N = {\large \prod}\limits_{i = 1}^k \, p_i^{\alpha_i} \ (\forall i ,\, p_i\in \mathbb P ,\, a_i \in \mathbb{N^*})\) 的形式，那麼：

特別地，\(\varphi(1) = 1\) 。

性質 \(\&\) 定理

有一堆，慢慢看吧，理性瞭解，證明的話有興趣可以自己去搜尋。

• 對於質數 \(p\)，\(\varphi(p) = p - 1\) 。
• 若 \(p\) 為質數，\(n = p^k \ (k \in \mathbb{N^*})\) ，那麼 \(\varphi(n) = p^k - p^{k - 1}\) 。
• 若 \(a \mid n\)，那麼 \(\varphi(an) = a \varphi(n)\) 。
• 若 \((n, m) = 1\) ，那麼 \(\varphi(n) \varphi(m) = \varphi(nm)\) 。
• 當 \(n > 2\) 時，\(\varphi(n)\) 為偶數。
• 若 \(n\) 為大於 \(1\) 的正整數，那麼在小於等於 \(n\) 的正整數中，與 \(n\) 互質的數之和為 \(\dfrac{n \varphi(n)}{2}\) 。
• $ n = {\large \sum}\limits_{d \mid n} , \varphi(d)$ 。

\(4.\) 線性篩法求尤拉函數 \(\varphi\)

利用線性篩法以及尤拉函數的性質，可以篩出 \([1,\, n]\) 內的所有質數，順便求出 \([1,\, n]\) 內的所有整數的尤拉函數，時間複雜度為 \(\mathcal O (n)\) 。

int primes[N], cnt;
int phi[N];
bool st[N];

void init(int n){
    phi[1] = 1;
    for(int i = 2; i <= n; ++i){
        if(!st[i]){
            primes[cnt++] = i;
            phi[i] = i - 1;
            // 前面的性質1
        }
        for(int j = 0; primes[j] * i <= n && j < cnt; ++j){
            st[primes[j] * i] = 1;
            if(i % primes[j] == 0){
                phi[i * primes[j]] = phi[i] * primes[j];
                // 性質3
                break;
            }
            phi[i * primes[j]] = phi[i] * (primes[j] - 1);
            // 這個可以直接由計算方法推出來
        }
    }
}

\(5.\) 尤拉定理

\(\text{Content}\)

若 \(a, n \in \mathbb{N^*}\) ，且 \((a, n) = 1\) ，則有：

\[\large a^{\varphi(n)} \equiv 1 \pmod n \]

特別地，當 \(n \in \mathbb P\) 時，這就成了費馬小定理

若 \(p \in \mathbb P\) ，且 \(p \nmid a\) 則有：

\[\large a^{p - 1} \equiv 1 \pmod p \]

\(6.\) 綜合應用

\(\texttt{E}\color{red}{\texttt{g} 1}\)

給定整數 \(N\)，將 \(N!\) 分解質因數，按照算術基本定理的形式輸出分解結果中的 \(p_i\) 和 \(c_i\) 。

按照 \(p_i\) 由小到大的順序輸出。

• \(3 \le N \le 10^6\)

首先 \(N \le 10^6\) ，所以 \(N!\) 會很大，直接分解肯定不行，考慮從 \(N!\) 的特殊性質入手。

\(N! = 1 \times 2 \times \cdots \times N\)

那麼對於一個質數 \(p\) ，\(1 \sim N\) 中的 \(p,2p,\dots,kp\) （ \(p\) 的倍數）肯定含有質因子 \(p\) ，可以很容易得出個數為 \(\left\lfloor \dfrac Np \right\rfloor\) 。

但這還會漏掉一些，如果一個數中含有 \(2\) 個因子 \(p\) ，會被漏算一次，因此還需要加上 \(1 \sim N\) 中的 \(p^2,2p^2,\dots,kp^2\) ，有 \(\left\lfloor \dfrac N{p^2} \right\rfloor\) 個。

以此類推，\(N!\) 中某個質因子 \(p\) 的次數為

那麼接下來列舉所有小於等於 \(N\) 的質數，再分別求和就好了，時間複雜度 \(\mathcal O(N)\) 左右吧（有點不好分析，反正過肯定是沒問題的）。

\(\mathcal{Code}\)

#include <cstdio>

using namespace std;
typedef long long ll;

const int N = 1e6 + 10;

int n;
int primes[N], cnt;
bool st[N];

void init(int n){
	for(int i = 2; i <= n; ++i){
		if(!st[i]) primes[cnt++] = i;
		for(int j = 0; primes[j] * i <= n && j < cnt; ++j){
			st[primes[j] * i] = 1;
			if(i % primes[j] == 0) break;
		}
	}
}

int main(){
	scanf("%d", &n);
	init(n);
	
	for(int i = 0; i < cnt; ++i){
		int p = primes[i], s = 0;
		int k = n;
		while(k){
			s += k / p;
			k /= p;
		}
		printf("%d %d\n", p, s);
	}
	
	return 0;
}

\(\texttt{E}\color{red}{\texttt{g} 2}\) 洛谷P2158 [SDOI2008] 儀仗隊

作為體育委員，C 君負責這次運動會儀仗隊的訓練。儀仗隊是由學生組成的 \(n \times n\) 的方陣，為了保證隊伍在行進中整齊劃一，C 君會跟在儀仗隊的左後方，根據其視線所及的學生人數來判斷隊伍是否整齊（如下圖）。

現在，C 君希望你告訴他隊伍整齊時能看到的學生人數。

• 對於 \(100 \%\) 的資料，\(1 \le n \le 40000\)。

首先進行分析，將儀仗隊放在一個平面直角座標系中，無法看到的學生是因為被在同一條從原點出發的直線上的前面的學生擋住了。

那麼可以得到學生能被看到的條件是橫縱座標互質。

答案就是：

最後加上的兩個是 \((0,1)\) 和 \((1,0)\) 。

上式變一下（配合著圖可能更好理解一些）：

這裡我們驚喜的發現，可以用 \(\varphi(i)\) 來表示 \({\Large \sum}\limits_{j = 1}^{i} \, [\gcd(i, j) = 1]\)

於是，最後的柿子就出來咯：

當然，當 \(n = 1\) 時，是沒有學生的，也不滿足上面的結論，需要特判一下。

程式碼就很好實現啦，用線性篩求個尤拉函數就可以 \(\color{#52C41A}{\text{AC}}\) 此題，\(\mathcal O(n)\) 根本不虛。

\(\mathcal{Code}\)

#include <iostream>
#include <cstring>
#include <cstdio>

using namespace std;
typedef long long ll;

const int N = 40010;

int T, n, res = 1;	// +1跑到這裡來了哦
int primes[N], cnt;
int phi[N];
bool st[N];

void init(int n){
	phi[1] = 1;
	for(int i = 2; i <= n; ++i){
		if(!st[i]){
			primes[cnt++] = i;
			phi[i] = i - 1;
		}
		for(int j = 0; primes[j] * i <= n && j < cnt; ++j){
			st[primes[j] * i] = 1;
			if(i % primes[j] == 0){
				phi[i * primes[j]] = phi[i] * primes[j];
				break;
			}
			phi[i * primes[j]] = phi[i] * (primes[j] - 1);
		}                          
	}
}

int main(){
	scanf("%d", &n);
	if(n == 1){
		puts("0");
		return 0;
	}
	init(n);
	
	for(int i = 1; i < n; ++i) res += 2 * phi[i];
	
	printf("%d\n", res);
	return 0;
}

蒟蒻很弱，如有錯漏還請各位大佬指出

感謝~~~