定义：$a,b\in Z,a\ne 0$，若
-
试除法判定质数
bool is_prime(int x) { if (x < 2) return false; for (int i = 2; i <= x / i; i ++ ) // 注意这里的循环判定条件 防止i * i<=n爆int if (x % i == 0) return false; return true; }
时间复杂度：$O(\sqrt n)$。
-
分解质因数
质因数(素因数或质因子)在数论里是指能整除给定正整数的质数。
除了1以外，两个没有其他共同质因子的正整数称为互质。因为1没有质因子，1与任何正整数（包括1本身）都是互质。
正整数的因数分解可将正整数表示为一连串的质因子相乘，质因子如重复可以用指数表示。
根据算术基本定理，任何正整数皆有独一无二的质因子分解式。只有一个质因子的正整数为质数。
每个合数都可以写成几个质数（也可称为素数）相乘的形式 ，这几个质数就都叫做这个合数的质因数。
void divide(int x) { for (int i = 2; i <= x / i; i ++ ) if (x % i == 0) { int s = 0; while (x % i == 0) x /= i, s ++ ; cout << i << ' ' << s << endl; } if (x > 1) cout << x << ' ' << 1 << endl; cout << endl; }
-
筛质数
埃氏筛法
从2开始，把每个数的倍数删掉(用st标记)，这样遍历2~n，没有被标记的数就是质数。
对于i，因为从2~i - 1的倍数都被删掉了了，如果这个数没有删掉，说明它在2~i - 1内没有因子，也就是说它是质数。
O(nlog logn) int primes[N], cnt; // primes[]存储所有素数 bool st[N]; // st[x]存储x是否被筛掉 void get_primes(int n) { for (int i = 2; i <= n / i; i ++ ) { if (st[i]) continue; // 已经被筛掉 primes[cnt ++ ] = i; for (int j = i + i; j <= n; j += i) // 标记所有i的倍数 // for (int j = i * i; j <= n; j += i) st[j] = true; } }
线性筛法
核心：每个数只有一个最小质因子，且会被他的最小质因子筛掉。
首先需要判断 i 是质数还是合数，如果是质数就将它放入primes[] 数组。
在第二个for循环中，将primes[j]的 i 倍筛掉（i 是从小到大依次遍历）
若存在一个合数X，设primes[j] 是它的最小质因子，当 i 枚举到X之前，一定会先枚举到X / primes[j]，而在那时，就已经先将X筛掉了。所以任何一个合数一定会被筛掉，是因为我们只用最小质因子来筛，但每个数只有一个最小质因子，所以每个数都只会筛一遍。例如 X = 12，2是12的最小质因子，在枚举到12之前一定会先枚举到6，并执行了st[2 * 6] = true，所以 i == 12 时，不会进入primes[j]数组 ；
最后的if语句有两种情况：
（1）若 i % primes[j] == 0 ，则说明 i 之前已经被 prime[j]筛过了（是最小质因子），i 再乘上更大的质数一定会被prime[j]的倍数筛掉，不需要在这里先筛掉（我们只用每个数的最小质因子筛），直接break 例如：4 % 2 == 0 ，2 是 4的最小质因子，且 2 也是2 * 4 的最小质因子（即 8 留到后面再筛）。
（2）若i % primes[j] != 0 ，由于我们是从小到大枚举的所有的质数，并且我们没有枚举到 i 的任何一个质因子，则此时primes[j] 一定小于 i 的所有质因子，但是primes[j] 也一定是primes[j] * i 的最小质因子。
//首先定义一个数组primes[]用来存放质数，cnt用来记录质数个数 //st[]用来标记这个数是否被筛掉 void get_primes(int n){ for(int i = 2; i <= n; i++ ){//筛选出2~n之间的质数 if(!st[i]) primes[cnt ++ ] = i;//如果没有被标记，则它一定是质数，将其放入primes[]数组 for(int j = 0; primes[j] <= n / i; j++ ){//从小到大枚举的所有质数 依次删除所有质数的2倍的合数，3倍的合数，4倍的合数.... st[primes[j]*i] = true; if(i % primes[j] == 0) break;//即 i 之前已经被 prime[j]筛过了，i在乘上更大的质数一定会被prime[j]的倍数筛掉，不需要在这里先筛掉（我们只用每个数的最小质因子筛），直接break } } }
-
互质
互质 ：公约数只有 1。 即如果
$\gcd(a,b)=1$ ，则称$a$ 和$b$ 互质。注意：多个数互质，不一定两两互质，如6、10、15。$\gcd(6,10, 15)=1$。
约数，又叫因数(因子)。整数
-
试除法求约数
// 暴力做法 vector<int> get_divisors(int a) { vector<int> ans; for (int i = 1; i <= a; i ++ ) { if (a % i == 0) ans.push_back(i); } return ans; } //这种做法当a很大时就会超时，时间复杂度较高 // 采用求质数的方法优化 // a = b * c, 一个数的约数是成对的，一大一小(两个相等的约数除外，如5 * 5 = 25)，所以我们可枚举所有的‘小’的约数 b，然后大的约数就可以直接用 a / b = c 求出来，最后对数组排序就行。同时对于可以开根号的数注意不要把两个相同的数都放进数组。 vector<int> get_divisors(int x) { vector<int> res; for (int i = 1; i <= x / i; i ++ ) if (x % i == 0) { res.push_back(i); if (i != x / i) res.push_back(x / i); } sort(res.begin(), res.end()); return res; }
-
约数个数、约数之和
对于任意数 N， 都有
N = p1^c1 * p2^c2 * ... * pk^ck。 约数个数：
(c1 + 1) * (c2 + 1) * ... * (ck + 1)，每一个质因数及其幂次方都是 N 的约数。 约数之和：(p1^0 + p1^1 + ... + p1^c1) * ... * (pk^0 + pk^1 + ... + pk^ck)。对于$n$ 来说，约数除了$p_1^0,p_1^1,...p_k^ak$ 这些质因数及其幂次方（一共只有$a_1+1 +a_2+1...a_k+1$ 个），不同质因数以及幂次方之间的乘积也是$n$ 的约数。二者加起来一共$(a_1+1)(a_2+1)+...+(a_k+1)$ 个。所以约数之和就是$sum = (p_1^0+p_1^1+...+p_1^{a_1})(p_2^0+p_2^1+...+p_2^{a_2})\cdot\cdot\cdot(p_k^0+p_k^1+...+p_k^{a_k})$ ，即每个质因数及其幂次方的乘积也要计算在内（把括号展开）。 -
最大公约数
最大公约数：一组整数的最大公约数，是指所有公约数里面最大的一个。
-
更相减损术
主要用于大整数（高精度）。
核心：大数减小数，直至二者相等。
int gcd(int a, int b) { while (a != b) { if (a > b)a -= b; else b -= a; } return a; }
-
欧几里得算法
递归写法
// Version 1 int gcd(int a, int b) { if (b == 0) return a; return gcd(b, a % b); } // Version 2 int gcd(int a, int b) { return b == 0 ? a : gcd(b, a \\% b); }
时间复杂度：O(log(max(a, b)))，计算过程：
当$a<b$的时候，$\gcd(a,b)=\gcd(b,a\% b)$，$a'=b,b'=a\% b\in(0,b-1)$，此时的$a' > b'$。
而对于$a>b$的情况：
- 当$a>2b$时：$\gcd(a,b)=\gcd (b, a\% b)$，$a'=b,b'=a\% b$，$b'\in(0,b-1)<\frac{a}{2}$，即
$a$ 的大小至少减半，所以时间复杂度为$O(\log(n))$ ； - 当$a = {2b}$时：$\gcd(a,b)=\max(2,b)$，时间复杂度为
$O(1)$ 。 - 当$a <{2b}$时：$\gcd(a,b)=\gcd(b,a\% b)$，$a'=b,b'=a\% b\in(0,b-1)$，此时
$\gcd(a',b')$ 又变成$a>b$，即最坏情况下时间复杂度为$O(2\log(n))$ ；
综上，时间复杂度为:
$\log(n)$ 。迭代写法
int gcd(int a, int b) { while (b != 0) { int tmp = a; a = b; b = tmp % b; } return a; }
- 当$a>2b$时：$\gcd(a,b)=\gcd (b, a\% b)$，$a'=b,b'=a\% b$，$b'\in(0,b-1)<\frac{a}{2}$，即
-
多个数的最大公约数
每次取两个数计算，将上一步的最大公约数与下一个数继续计算，直到计算完所有数。
-
最小公倍数
对于两个数，它们的最小公倍数等于两数之积除以最大公约数。
$0$ 是任意一组整数的公倍数。$\gcd(a,b)\times \operatorname {lcm}(a,b)=a\times b$ 。int lcm(int a, int b) { return a / gcd(a, b) * b; }
多个数的最小公倍数：先求前两个数的最小公倍，再用这个最小公倍数与下一个数求最小公倍数，直到结束。
-
扩展欧几里得
扩展欧几里得算法（Extended Euclidean algorithm, EXGCD），常用于求
$ax+by=\gcd(a,b)$ 的一组可行解。解：$x = y',y = x'-\lfloor\frac{a}{b}\rfloor y'$。一直递归到
$x=1,y=0$ int exgcd(int a, int b, int x, int y) { if (!b) { x = 1, y = 0; return a; // gcd(a, 0) 即最大公约数 } int d = exgcd(b, a % b, x, y); int t = x; x = y; y = t - a / b * y; return d; // gcd(a, b) 最大公约数 }
-
以 c++ 语言为例：取模的符号即与被除数相同。
5 % 3 == 2;
5 % -3 == 2;
-5 % 3 == -2;
-5 % -3 == -2;-
概念
欧拉函数：$\varphi(N)$，表示 1~N 中与 N 互质的数的个数。n 是质数的时候，$\varphi(n)=n-1$。欧拉函数是积性函数：$\varphi(a\times b)=\varphi(a)\times \varphi(b)$。n 是奇数时，$\varphi(2n)=\varphi(n)$。
对于N，N =
$\ p_1^{a1}p_2^{a2}p_3^{a3}.....p_k^{ak}$ ，Φ(N) =$N * \frac{p1 - 1}{p1} * \frac{p2 - 1}{p2} *...*\frac{pk - 1}{pk}$ 每一个数字都可以表示为k个质数(质因子)的
$a_i$ 次方的乘积（即因式分解）。时间复杂度O(
$\sqrt{n}$ )int eulor_phi(int n) { int ans = n; for (int i = 2; i <= n / i; i ++) { if (n % i == 0) { ans = ans / i * (i - 1); while (n % i == 0) n /= i; } } if (n > 1) // 对于任意数a，大于根号n的质因子最多有一个，否则质因子平方会大于a，矛盾了。 ans = ans / n * (n - 1); return ans; }
-
线性筛法求欧拉函数
求多个数的欧拉函数值。
核心思想：用每一个合数的最小质因数来筛掉合数。
int prime[N]; // 质数 bool vis[N]; int phi[N]; //欧拉函数值 void euler(int) { int cnt = 0; for (int i = 2; i <= n; i ++) { if (!vis[i]) { prime[cnt ++] = i; phi[i] = i - 1; } for (int j = 0; prime[j] <= n / i; j ++) { vis[prime[j] * i] = true; if (i % prime[j] == 0) { phi[prime[j] * i] = phi[j] * prime[j]; break; } phi[prime[j] * i] = phi[i] * (prime[j] - 1); } } }
在筛质数的过程中，对于质数 a，其欧拉函数为 a - 1。
对于非质数： 如果
$i % prime[j] == 0$ ，即$prime[j]$ 是$i$ 的质因数，因为欧拉函数包含两部分：原数字$n$ 和后面的分式，所以计算$prime[j] * i$ 的欧拉函数后面得分式就等于计算$i$ 得欧拉函数得分式，（$prime[j]$ 是$prime[j] * i$ 的质因数），变得是前面的原数字，即再乘上一个$prime[j]$ 。 如果$i % prime[j] != 0$ ，即$prime[j]$ 不是$i$ 的质因数，则$\varphi(prime[j]*i)=\varphi(prime[j])\varphi(i)$ ，即$(prime[j]- 1)*phi[i]$ 。 -
欧拉定理
如果
$\gcd(a,m)=1$ ，则$a^{\varphi(m)}\equiv1(\mod m)$。特别地，当$m$ 是质数的时候，则$a^{\varphi(m)}=a^{m-1}\equiv1(\bmod m)$ 。
-
取模定理
(a + b) % p = (a % p + b % p) % p (a - b) % p = (a % p - b % p ) % p (a * b) % p = (a % p * b % p) % p 可以从 a、b 扩展到 n 个
-
快速幂
核心思想：每一步都把指数分成两半，而相应的底数做平方运算。
指数是偶数：直接除以 2 ，指数是奇数：结果先乘一个底数，再把指数除以2
求 m^k mod p，时间复杂度
O(logk)。// 传统方法 int a, k; // a底数 k指数 int sum = 1; for (int i = 1; i <= k; i ++ ) { sum = sum * k % mod; } 缺陷： 1、数加大时超过int、longlong 2、当 k 较大时(1e9)，会超时 // 改进 typedef long long LL; int f_Power(LL m, LL k, LL p) { LL res = 1, t = m; while (k) { if (k&1) // 奇数 res = res * t % p; t = t * t % p; k / = 2; // 一半 } return res; }
对于任意的整数对$a$，$b$，且
推论：a，b互质的充要条件：存在整数
求裴蜀定理特例的解：$ax+by=\gcd(a, b)$ ，求
当
void exgcd(int a, int b, int& x, int& y) { // x、y传得是引用 值可以改变
if (b == 0) {
x = 1;
y = 0;
return ;
}
exgcd(b, a % b, x, y); // 递归完成后，x、y已经变成了 bx+a%b*y=gcd(b,a%b) 新方程的解
int t = x;
x = y;
y = t - a / b * y;
}-
a mod m = b mod m <---> (a-b) % m = 0
定义：两个整数
a和b，若它们除以正整数m所得的余数相等，则称a与b对模m同余或a同余于b模m。记作a ≡ b(mod m)<--->a % m=b % m。充要条件：$a - b$ 能被
$m$ 整除（即m|a-b）。证明:
$a=m\cdot q_1+r,b=m\cdot q_2+r$ ，$a-b=m(q_1-q_2)$，即$a-b$ 能被$m$ 整除。性质
-
相加：$a_1≡b_1(\mod\ m),a_2≡b_2(\mod\ m),...,a_n≡b_n(\mod m)$，则
$a_1+a_2+...+a_n≡b_1+b_2+...+b_n(mod\ m)$ ； -
相乘：$a_1≡b_1(\mod\ m),a_2≡b_2(\mod\ m),...,a_n≡b_n(\mod m)$，则
$a_1a_2...a_n≡b_1b_2...b_n(mod\ m)$ ； -
等式两边移项：$a+b\equiv c(\mod m)$，则
$a\equiv c - b(\mod m)$ ； -
如果
$a≡b(mod\ m)$ ，则$b≡a(mod\ m)$ ； -
传递性：如果
$a≡b(mod\ m),b≡c(mod\ m)$ ，则$a≡c(mod\ m)$ ；
-
相加：$a_1≡b_1(\mod\ m),a_2≡b_2(\mod\ m),...,a_n≡b_n(\mod m)$，则
-
(a+b)%m = (a%m+b%m)%m
(a*b)%m = ((a%m)*(b%m))%m
-
线性同余方程
对于整数
$a$ ，存在$x$ ，使得$a\times x \equiv b\ (\mod m)$ ，即$a$ 与$x$ 的乘积模上$m$ 的余数是$b$ 。求该方程的解就是求$x$ 。该方程称为 线性同余方程。$a\times x\ %\ m = b$ 等价于$a\times x-b$ 是$m$ 的倍数：$a\times x - b = m\times y'$。 格式类似于扩展欧几里得方程：$a\times x + b\times y = c$，其中$c$ 是$gcd(a, b)$ 的倍数，特例，存在一组解：$a\times x_0 + b \times y_0 = gcd(a, b)$。 再来看：$a\times x - b = m\times y'$，即：$a\times x - m\times y' = b$，其实就是$a\times x + m\times y = b$ 的一组特解（而且，本题求得是$x$ ，所以$y$ 的正负其实无所谓）。 所以我们可以先用扩展欧几里得求出$a\times x + m\times y = gcd(a, m)$ 的解，然后等式两边乘上$\frac{b}{gcd(a,m)}$ 就是$a\times x\cdot \frac{b}{gcd(a,m)} + m\times y\cdot \frac{b}{gcd(a,m)} = gcd(a, m)\cdot \frac{b}{gcd(a,m)}$ ，即本题的解：$\mathbf x = x\frac{b}{gcd(a,m)}$此外，方程有整数解的充要条件为
$\gcd(a,m)|b$ ，即上面的解的后半部分必须是整数。
n 的阶乘：$n! = 1\times 2 \times 3...\times n = 2^a \times 3^b \times 5^c...$，分解质因数。
任何一个大于等于 2 的 数都能分解成质因数幂乘积。
质因数中只有 2 和 5 的乘积 10 含有 0，所以阶乘结果的后面的 0 的个数由 2 和 5 决定。一对 2 和 5 贡献一个 0， 则阶乘结果的后面的 0 的个数等于 2 和 5 中数量较少的那个。求阶乘结果的后面的 0 的个数等价于求 2 和 5 数量的较小值。
乘法逆元的定义：若整数
另一种定义形式：如果一个线性同余方程
判断条件： 存在乘法逆元的充要条件是 m 为质数时， 即为
费马小定理：假如
如果
注意：使用费马小定理求得时候模数必须是质数。
当
根据欧拉定理，$a^{\varphi(m)}\equiv 1(\bmod m)$，求
void exgcd(int a, int b, int& x, int& y) {
if(!b) {
x = 1, y = 0;
return ;
}
exgcd(b, a % b, y, x); // 注意这里传的参数 使得 y = x' x = y'
y -= a / b * x; // 最终的x = y' y = x'-a/b*y'
}
//version 2 不省略
int exgcd(int a, int b, int& x, int& y) { // 返回a、b最大公约数
if (!b) {
x = 1, y = 0;
return a;
}
int d = exgcd(b, a % b, x, y);
int t = x;
x = y;
y = t - a / b * y;
}主要用于求多个数的逆元：求出
如果对于每个数进行单次求解，以上两种方法就显得很慢，可能超时，用线性法求逆元更快。
时间复杂度：$O(n)$。
首先，$1^{-1}\equiv1(\bmod p)$；（因为
待更。。。。
中国剩余定理 (Chinese Remainder Theorem, CRT) 可求解如下形式的一元线性同余方程组：$\left {\begin{aligned} x & \equiv a_{1}\left(\bmod n_{1}\right) \ x & \equiv a_{2}\left(\bmod n_{2}\right) \ & \vdots \ x & \equiv a_{k}\left(\bmod n_{k}\right) \end{aligned}\right.$
其中，$n_1,n_2,...,n_k$ 两两互质。解题过程如下：
- 计算所有模数的积
$n=n_1*n_2...n_k$ ； - 对于第 i 个方程：
- 计算
$m_i=\frac{n}{n_i}$ ； - 计算
$m_i$ 在模$n_i$ 意义下的逆元$m_i^{-1}$ ；($m_i、n_i$ 一定是互质的（也就是方程组一定有解），因为$m_i$ 的因数不包括$n_i$ ，$n_i$ 的因数只有自身，所以二者只有公因数 1) - 计算
$c_i=m_im_i^{-1}$ （不要对$n_i$ 取模)
- 计算
- 方程组在模
$n$ 意义下的唯一解为：$x=\sum^k_{i=1}a_ic_i(\mod n)$
代码实现
LL CRT(int k, vector<int> a, vector<int> r) { // r 是模数
LL n = 1, ans = 0;
for (int i = 1; i <= k; i ++) n *= r[i];
for (int i = 1; i <= k; i ++) {
LL m = n / r[i], x, y;
exgcd(m, r[i], x, y); // x * m mod r[i] = 1--mx+r[i]y = 1
ans = (ans + a[i] * m * x % n) % n;
}
return (ans % n + n) % n;
}模数不互质的情况
-
两个方程的情况
设方程分别为
$x\equiv a_1(\bmod m_1)、x\equiv a_2(\bmod m_2)$ ；转化为不定方程：$x=m_1p+a_1=m_2q+a_2$，p、q 是整数，则
$m_1p-m_2q=a_2-a_1$ 。转换为裴蜀定理：$m_1p+m_2(-q)=a_2-a_1$根据[裴蜀定理](#1. 裴蜀定理)，当
$a_2-a_1$ 不能被$\gcd(m_1,m2)$ 整除时，无解；否则，可通过扩展欧几里得求出一组解
$(p,q)$ ；则原来的两方程组成的模方程组的解为
$x\equiv b(\bmod M)$ ，其中$b=m_1p+a_1$ ，$M=\operatorname {lcm}(m_1,m_2)$。 -
多个方程的情况
先求前两个方程得到解，再用得到的解与第三个方程求解，直到求出最终结果。
代码不会
若函数
若函数