基础数论

1. 因子（约数）

1.1 因子的定义

• $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)$。



参考代码



~~~cpp
#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))$，非常快。



参考代码



~~~cpp
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$ 是否存在因子。



参考代码



~~~cpp
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 参考代码



~~~cpp
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 参考代码（线性筛 + 最小质因子）



~~~cpp
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 定理内容



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

• $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$