1. 质数

1.1 质数的判定

试除法

若一个正整数$N$为合数（除了能被1和自身以外的数整除），则存在一个能整除$N$的数$T$，其中$2\leq T\leq \sqrt N$。

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

1.2 质数的筛选

Eratosthenes筛法

基本思想：任意整数$x$的倍数$2x, 3x, ...[N/x]*x$都不是质数。

void primes(int n)
{memset(v, 0, sizeof(v)); //合数标记for (int i = 2; i <= n; ++ i ){if (v[i]) continue;cout << i << endl; // i是质数for (int j = i; j <= n/i; ++ j ) v[i*j] = 1;}
}

Eratosthenes筛法的时间复杂度为$O(NloglogN)$。该算法效率非常接近线性。

线性筛法

线性筛法通过“从大到小累计质因子”的方式标记合数，即让12只有$3*2*2$一种产生方式。

int primes[N], cnt = 0;     // primes[]存储所有素数
bool st[N];         // st[x]存储x是否被筛掉void get_primes(int n)
{for (int i = 2; i <= n; i ++ ){if (!st[i]) primes[cnt ++ ] = i;for (int j = 0; primes[j] <= n/i; j ++ ){st[primes[j] * i] = true;if (i % primes[j] == 0) break;}}
}

1.3 质因数分解

定理：任何一个大于1的正整数都能唯一分解为有限个质数的乘积，可写作：
$N = p^{c_1}_1p^{c_2}_2...p^{c_m}_m$
其中$c_i$都是正整数，$p_i$都是质数，且满足$p_1<p_2<...<p_m$。

试除法

void divide(int n)
{m = 0;for (int i = 2; i <= sqrt(n); ++ i ){if (n % i == 0){p[++m] = i, c[m] = 0;while (n % i == 0) n /= i, c[m]++;}}if (n > 1) // n是质数p[++m] = n, c[m] = 1;for (int i = 1; i <= m; ++ i )cout << p[i] << " " << c[i] << endl;
}

2.约数

定义：若整数$n$除以整数$d$的余数为0，即$d$能整出$n$，则称$d$是$n$的约数，记为$d|n$。

关于约数的一个定理：一个数有奇数个约数，那么这个数是平方数。

2.1 算术基本定理的推论

在算术基本定理中，若正整数$N$被唯一分解为$N = p^{c_1}_1p^{c_2}_2...p^{c_m}_m$,其中$c_i$都是正整数，$p_i$都是质数，且满足$p_1<p_2<...<p_m$,则$N$的正约数集合可以写作：
$\{p^{c_1}_1p^{c_2}_2...p^{c_m}_m\},其中0\leq b_i\leq c_i$
$N$的正约数个数为：
$(c_1+1)*(c_2+1)*...(c_m+1)=\prod^{m}_{i=1}(c_i+1)$
$N$的所有正约数的和为：
$(1+p_1+p_1^2+...+p_1^{c_1})*...*(1+p_m+p_m^2+...+p_m^{c_m}) = \prod^m_{i=1}(\sum^{c_i}_{j=0}(p_i)^j)$

2.2 求$N$的正约数集合—试除法

若$d\geq\sqrt N$是$N$的约数，则$N/d\leq \sqrt N$也是$N$的约数。换言之，约数是成对出现的（除了完全平方数）。

int factor[1600], m = 0;for (int i = 2; i*i <= n; ++ i )
{if (n % i == 0){factor[++m] = i;if (n/i != i) factor[++m] = n/i;}
}for (int i = 1; i <= m; ++ i )cout << factor[i] << endl;

试除法的推论

一个整数$N$的约数个数上界为$2\sqrt N$。

2.3 求$1 \sim N$每个数的正约数集合—倍数法

对于每个数$d$,$1\sim N$中以$d$为约数的数就是$d$的倍数$d,2d,...[n/d]*d$。

vector<int> factor[500010];for (int i = 1; i <= n; ++ i )
{for (int j = 1; j <= n/i; ++ j )factor[i*j].push_back(i);
}for (int i = 1; i <= n; ++ i )
{for (auto &x : factor[i]){cout << x << " ";}puts("");
}

上述算法的时间复杂度为$O(NlogN)$。

倍数法的推论

$1\sim N$每个数的约数个数的总和大约为$NlogN$。

2.4 最大公约数

定理：$\forall a,b\subset \N, gcd(a,b) *lcm(a,b)=a*b$。

欧几里得算法

int gcd(int a, int b)
{return b ? gcd(b, a%b) : a;
}

2.5 互质与欧拉函数

定义：$\forall a,b\subset \N, gcd(a,b) =1$，则称a,b互质。

欧拉函数

$1\sim N$中与$N$互质的数的个数被称为欧拉函数，记为$\varphi (N)$。

若在算术基本定理中，$N = p^{c_1}_1p^{c_2}_2...p^{c_m}_m$,则
$\varphi (N) = N*\frac{p_1-1}{p_1}*\frac{p_2-1}{p_2}*...*\frac{p_m-1}{p_m}=N*\prod_{质数p|N}(1-\frac{1}{p})$

int phi(int n)
{int ans = n;for (int i = 2; i < sqrt(n); ++ i ){if (n % i == 0){ans = ans*(i-1)/i;while (n % i == 0) n /= i;}}if (n > 1) ans = ans*(n-1)/n;return ans;
}

欧拉函数的常用性质：

1. 如果$n,m$互质，则$\varphi(nm) = \varphi(n)*\varphi(m)$。
2. $\forall n>1,1 \sim n$中与$n$互质的数的和为$n*\varphi(n)/2$。
3. 设$p$为质数，若$p|n$且$p^2|n$,则$\varphi(n)=\varphi(n/p)*p$。
4. 设$p$为质数，若$p|n$且$p^2\nmid n$,则$\varphi(n)=\varphi(n/p)*(p-1)$。
5. 欧拉定理：如果$a,n$互质，且均为正整数，则$a^{\varphi(n)} \equiv 1(mod \ n)$。

筛法求欧拉函数

int primes[N], euler[N], cnt;
bool st[N];// 质数存在primes[]中，euler[i] 表示
// i的欧拉函数
void get_eulers(int n)
{euler[1] = 1;for (int i = 2; i <= n; i ++ ){if (!st[i]){primes[cnt ++ ] = i;euler[i] = i - 1;}for (int j = 0; primes[j] <= n/i; j ++ ){st[primes[j] * i] = true;if (i % primes[j] == 0){euler[i * primes[j]] = euler[i] * primes[j];break;}euler[i * primes[j]] = euler[i] * (primes[j] - 1);}}
}

同余

定义：若整数$a$和$b$除以正整数$m$的余数相等，则称$a,b$模m同余，记为$a\equiv b(mod\ m)$。

费马小定理：

​ 若$p$是质数，而整数$a$不是$p$的倍数，有$a^p\equiv a(mod\ p)$。

欧拉定理:

​ 若正整数$a,n$互质，则$a^{\varphi(n)} \equiv 1(mod \ n)$，其中$\varphi(n)$为欧拉函数。

欧拉定理的推论：

​ 若正整数$a,b$互质，则对于任意正整数$b$，$a^b \equiv a^{b\ mod\ \varphi(n)}(mod \ n)$。

扩展欧几里得算法

裴蜀定理：

​ 对于任意整数$a,b$,存在一对整数$x,y$,满足$ax+by=gcd(a,b)$。

int exgcd(int a, int b, int& x, int& y)
{if (b == 0) { x = 1, y = 0; return a; }int d = exgcd(b, a%b, x, y);int z = x; x = y; y = z-y*(a/b);return d;
}

乘法逆元：

​ 若整数$b,m$互质，并且$b|a$，则存在一个整数$x$，使得$a/b\equiv a*x(mod\ m)$。称$x$为$b$的模$m$乘法逆元，记为$b^{-1}(mod\ m)$。

​ 因为$a/b\equiv a*b^{-1}\equiv a/b*b*b^{-1}(mod\ m)$，所以$b*b^{-1}\equiv 1(mod\ m)$。

​ 当模数m为质数时，$b^{m-2}$即为$b$的乘法逆元。如果只是保证$b,m$互质，那么乘法逆元可通过解同余方程$b*x\equiv 1(mod\ m)$得到。

线性同余方程

给定整数$a,b,m$，求一个整数$x$满足$a*x\equiv b(mod\ m)$，或者给出无解。因为未知数的指数为1，所以我们称之为一次同余方程，也称为线性同余方程。

$a*x\equiv b(mod\ m)$等价于$a*x-b$是$m$的倍数，不妨设为$-y$倍。于是，该方程可以改写为$a*x+m*y=b$。

根据前面裴蜀定理的证明，线性同余方程有解当且仅当$gcd(a,m)|b$。

中国剩余定理：

​ 设$m_1,m_2,...,m_n$是两两互质的整数，$m=\prod^n_{i=1}m_i,M_i=m/m_i,t_i$是线性同余方程$M_it_i\equiv 1(mod\ m_i)$的一个解。对于任意的$n$个整数$a_1,a_2,...,a_n$，方程组
$x\equiv a_1(mod\ m_1),x\equiv a_2(mod\ m_2),...,x\equiv a_n(mod\ m_n)$
​ 有整数解，解为$x=\sum^n_{i=1}a_iM_it_i$。

组合计数

排列数：

​ 从$n$个不同元素中依次取出$m$个元素排成一列，产生的不同排列的数量为：
$A^m_n=\frac{n!}{(n-m)!}$
组合数：

​ 从n个不同元素中取出m个组成一个集合（不考虑顺序），产生的不同集合数量为：
$C^m_n=\frac{n!}{m!(n-m)!}$
性质：

1. $C_n^m=c_n^{n-m}$

2. $C_n^m=c_{n-1}^m+c_{n-1}^{m-1}$

3. $C_n^0+C_n^1+...+C_n^n=2^n$

   递归法求组合数

   // c[a][b] 表示从a个中选b个的方案数
   for (int i = 0; i < N; i ++ )
   {for (int j = 0; j <= i; j ++ ){if (!j) c[i][j] = 1;else c[i][j] = (c[i - 1][j] + c[i - 1][j - 1]) % mod;   }
   }
   

   通过预处理逆元的方式求组合数

   // 首先预处理出所有阶乘取模的余数fact[N]，以及所有阶乘取模的逆元infact[N]
   // 如果取模的数是质数，可以用费马小定理求逆元
   int qmi(int a, int k, int p)    // 快速幂模板
   {int res = 1;while (k){if (k & 1) res = (LL)res * a % p;a = (LL)a * a % p;k >>= 1;}return res;
   }// 预处理阶乘的余数和阶乘逆元的余数
   fact[0] = infact[0] = 1;
   for (int i = 1; i < N; i ++ )
   {fact[i] = (LL)fact[i - 1] * i % mod;infact[i] = (LL)infact[i - 1] * qmi(i, mod - 2, mod) % mod;
   }
   

   多重集的排列数:

   ​ 多重集是指包含重复元素的广义集合。设$S=\{n_1*a_1,n_2*a_2,...,a_k*a_k \}$是由$n_1$个$a_1$，$n_2$个$a_2...n_k$个$a_k$组成的多重集。$S$的全排列个数为$\frac{n!}{n_1!n_2!...n_k!}$。

   多重集的组合数:

   ​ 从$S$中取出$r(r\leq n_i)$个元素组成一个多重集（不考虑元素的顺序），产生的不同多重集的数量为$C_{k+r-1}^{k-1}$。

   Lucas定理：

   ​