基础数论

1. 因子（约数）

1.1 因子的定义

如果整数 $d$ 能整除 $n$，也就是存在整数 $k$ 使得 $n=d\times k$，那么称 $n$ 是 $d$ 的倍数， $d$ 是 $n$ 的因子（约数），记作：

• $d\mid n$

例如：

• $1\mid 12$
• $6\mid 12$
• $12\mid 12$

---

1.2 枚举一个数的所有因子

枚举因子常用做法是从 $1$ 到 $\lfloor\sqrt n\rfloor$ 试除：

如果 $i\mid n$，那么：

• $i$ 是因子
• $\dfrac{n}{i}$ 也是因子

这样复杂度是 $O(\sqrt n)$。

参考代码

#include <bits/stdc++.h>
using namespace std;

vector<long long> get_divisors(long long n) {
    vector<long long> d;
    for (long long i = 1; i * i <= n; i++) {
        if (n % i == 0) {
            d.push_back(i);
            if (i != n / i) d.push_back(n / i);
        }
    }
    sort(d.begin(), d.end());
    return d;
}

---

2. 最大公约数 $\gcd$

2.1 定义

$\gcd(a,b)$ 表示 $a$ 和 $b$ 的最大公约数，即能同时整除 $a$ 和 $b$ 的最大整数。

例如：

• $\gcd(12,18)=6$

---

2.2 欧几里得算法（辗转相除法）

核心结论：

• $\gcd(a,b)=\gcd(b,a\bmod b)$

当 $b=0$ 时：

• $\gcd(a,0)=a$

复杂度为 $O(\log \min(a,b))$，非常快。

参考代码

long long gcd_ll(long long a, long long b) {
    return b == 0 ? a : gcd_ll(b, a % b);
}

---

2.3 常见性质

1. $\gcd(a,b)=\gcd(b,a)$
2. $\gcd(a,b)\le \min(a,b)$
3. 若 $d\mid a$ 且 $d\mid b$，则 $d\mid \gcd(a,b)$
4. $\gcd(a,b)=1$ 时称 $a,b$ 互质

---

3. 质数（素数）

3.1 定义

如果整数 $n\ge 2$，并且它只有两个正因子：$1$ 和 $n$，则 $n$ 是质数。

例如：

• $2,3,5,7,11$ 是质数
• $1$ 不是质数
• $4,6,8,9,10$ 不是质数

---

3.2 试除法判定质数

判定 $n$ 是否为质数，只需要检查 $2\sim \lfloor\sqrt n\rfloor$ 是否存在因子。

参考代码

bool isPrime(long long n) {
    if (n < 2) return false;
    for (long long i = 2; i * i <= n; i++) {
        if (n % i == 0) return false;
    }
    return true;
}

---

4. 埃氏筛

当题目需要求 $1\sim n$ 的所有质数时，可以使用筛法。

4.1 核心思想

• 初始化所有数都假设是质数
• 从 $2$ 开始遍历
• 如果 $i$ 是质数，就把它的倍数标记为合数

复杂度约为 $O(n\log\log n)$。

---

4.2 参考代码

const int N = 1e6;
bool st[N + 10];
int primes[N + 10];
void f(){
	for(int i = 2; i <= N; i++) {
		if(st[i]) continue;
		for(int j = i + i; j <= N; j += i) {
			st[j] = true;
		}
	}
}

---

5. 线性筛（欧拉筛）

线性筛可以在 $O(n)$ 的时间内求出 $1\sim n$ 的所有质数。

5.1 核心思想

每个合数都只会被它的“最小质因子”筛掉一次，因此总复杂度是 $O(n)$。

---

5.2 参考代码（线性筛 + 最小质因子）

int primes[10000010]; // 存质数表
int idx; 
bool st[N]; //记录状态

void f(int n) {
	st[1] = true; // true代表不是质数
	for(int i = 2; i <= n; i++){
		if(!st[i]) {
			primes[++idx] = i; 
		} 
		//筛的时候  c =  a * b    a是最小质因子   b是当前数字i
		for(int j = 1; primes[j] * i <= n; j++) {
			st[primes[j] * i] = true;
			if(i % primes[j] == 0) break;
		} 
	}	
}

---

5.3 线性筛的特点

1. 时间复杂度 $O(n)$
2. 可以快速得到所有质数列表 primes
3. 可以在筛法过程中得到每个数的最小质因子 minp，对分解质因数很有用

---

6. 唯一分解定理（算术基本定理）

6.1 定理内容

对于任意整数 $n>1$，它都可以写成若干个质数的乘积，并且这种分解在不考虑顺序时是唯一的：

• $n=p_1^{a_1}p_2^{a_2}\cdots p_k^{a_k}$

其中：

• $p_1,p_2,\dots,p_k$ 是互不相同的质数
• $a_1,a_2,\dots,a_k$ 是正整数

---

6.2 示例

• $60=2^2\times 3^1\times 5^1$
• $84=2^2\times 3^1\times 7^1$
• $72=2^3\times 3^2$

“唯一”指的是：
如果把 $60$ 分解成质因数，不管怎么写，最终一定是 $2^2\times 3\times 5$（顺序可以变，但质数和指数不会变）。

【前置知识点】
1、数学

【后置衔接知识点】
1、排列组合

【思维导图】

【题目知识点分类】