初等数论
题单介绍
1. 整除
> 对于整数a、b，若存在整数k，使得a=bk，那么称b整除a，a被b整除。记做b|a。
2. 因数
> 对于正整数a、b，若b|a，那么b称作a的因数。
3. 倍数
> 对于整数a、b，若b|a，那么a称作b的倍数。
4. 质数
> 对于正整数a，若小于a的正整数中有且只有1为a的因数，那么a称作质数。
5. 合数
> 对于正整数a，若小于a的正整数中不止1个因数，那么a称作合数。
6. 同余
> 对于正整数a、b、p，若存在正整数x、y、z，使得a=xp+z,b=yp+z，那么称a与b在模p的情况下同余。记做$a \equiv b (mod \ p)$
7. 唯一分解定理
> 对于任何一个正整数，都可以唯一分解成有限个质数的乘积。
8. 欧几里得算法（辗转相除法）
> 易证明gcd(a,b)=gcd(b,a mod b) (gcd为最大公约数)。所以可写出以下代码求最大公约数。
```cpp
int gcd(int x,int y){
if(y==0)return x;
return gcd(y,x%y);
}
```
9. 素数筛
```cpp
int Eratosthenes(int n) {//埃氏筛法
int p = 0;
for (int i = 0; i <= n; ++i) is_prime[i] = 1;
is_prime[0] = is_prime[1] = 0;
for (int i = 2; i <= n; ++i) {
if (is_prime[i]) {
prime[p++] = i; // prime[p]是i,后置自增运算代表当前素数数量
for (int j = i * i; j <= n;
j += i) // 因为从 2 到 i - 1 的倍数我们之前筛过了，这里直接从 i
// 的倍数开始，提高了运行速度
is_prime[j] = 0; //是i的倍数的均不是素数
}
}
return p;
}
```
```cpp
void init() {//线性筛法,phi为欧拉函数
phi[1] = 1;
for (int i = 2; i < MAXN; ++i) {
if (!vis[i]) {
phi[i] = i - 1;
pri[cnt++] = i;
}
for (int j = 0; j < cnt; ++j) {
if (1ll * i * pri[j] >= MAXN) break;
vis[i * pri[j]] = 1;
if (i % pri[j]) {
phi[i * pri[j]] = phi[i] * (pri[j] - 1);
} else {
// i % pri[j] == 0
// 换言之，i 之前被 pri[j] 筛过了
// 由于 pri 里面质数是从小到大的，所以 i 乘上其他的质数的结果一定会被
// pri[j] 的倍数筛掉，就不需要在这里先筛一次，所以这里直接 break
// 掉就好了
phi[i * pri[j]] = phi[i] * pri[j];
break;
}
}
}
}
```
[题单1](https://www.luogu.com.cn/training/6358)
（题单里的题未经过筛选和排序）