整除
定义
若 $ a = bk $ , 其中 $ a in Z, b in Z, k in Z $, 则称 $ b $ 整除 $ a $ , 记做 $ b | a $.
也称 $ b $ 是 $ a $ 的约数(因数), $ a $ 是 $ b $ 的倍数
性质
((1)) $ 1 $ 整除任何数 $ ( 1 | k ) , k in Z$ , $ 0 $ 被任何数整除 $ ( k | 0), k in Z $
((2)) 若 $ a | b $ 且 $ a | c $, 则 $ a | (b + c), a | (b - c)$
((3)) 若 $ a | b $, 则对于任意整数 $ c $ , $ a | bc $
((4)) 传递性：若 $ a | b $ 且 $ b | c $ , 则 $ a | c $
((5)) 有待添加(其实是太多了,不想证)
例题
质数和合数
定义
质数又称素数(下文中不区分质数和素数)
设 $ p in Z_+ $
((1)) 当且仅当 $ p > 1 $ 且只能被 $ 1 $ 和 $ p $ 整除(即 $ p $ 仅有两个因子 $ 1 $ 和 $ p $ ), 则称 $ p $ 是一个质数;
((2)) 否则, 若 $ p > 1 $ , 则称 $ p $ 是一个合数;
((3)) 当 $ p = 1 $, $ p $ 既不是质数也不是合数.
性质
((1)) 质数有无穷多个.
((2)) 若 $ n $ 是一个合数, 则 $ n $ 至少有一个质因子.
((3)) 若 $ n $ 是一个合数, 其中最小的质因子一定不大于 $ sqrt n $
((4)) 若 $ n $ 是一个合数, 不大于 $ n $ 的质数约有 $ dfrac{n}{ln n} $ 个.
唯一分解定理
把正整数 $ n $ 写成质数的乘积
$ n = p_1^{a_1}p_2^{a_2}p_3^{a_3}...p_k^{a_k} $, 其中 $ p_i $ 为质数, $ a_i $ 为正整数
这样的表示是唯一的.
试除法
最简单的判断一个数(n)是否为质数的方法
只需要从 $ 2 $ 除到 $ sqrt n$ 即可, 如果中间有整数能整除 (n) 则 (n) 是合数, 反之 $ n $ 是质数
例题
[CF 776B] Sherlock and his girlfriend
同余
定义
对于整数 (a, b, b > 0), 则存在唯一的整数 (q, r) 满足 (a = bq + r)
其中 $0 leqslant r < b $。
其中称 (q) 为商, $ r $ 为余数。
余数用 $ a mod b $ 表示。
若两数 (a, b) 除以 (c) 的余数相等,则称(a,b) 模 $ c $ 同余，记做 (a equiv b pmod{c})。
性质
((1)) $a equiv b pmod{c} Leftrightarrow c | ( a − b ) $
推论：若 (a equiv b pmod{c}, d|c), 则 (a equiv b pmod{d})
((2)) 有待添加(其实是太多了,不想证)
最大公约数
定义
设 (a, b) 是不都为 (0) 的整数, (c) 为满足 (c | a) 且 (c | b) 的最大整数.
则称 (c) 是 (a, b)的最大公约数
记为 (gcd(m, n)) 或 ((a, b))
若((a, b) = 1), 则称 (a, b) 互质(互素)
性质
((1)) ((a, a) = (0, a) = a)
((2)) 若 (a|b) , 则((a, b) = a)
((3)) ((a, b) = (a, a + b) = (a, ka + b))
((4)) ((ka, kb) = k imes (a, b))
((5)) ((a, b, c) = ((a , b), c))
求gcd
求 (GCD) 的一般公式:质因数分解
$ a = p_1^{a_1}p_2^{a_2}p_3^{a_3}...p_k^{a_k} $
$ b = p_1^{b_1}p_2^{b_2}p_3^{b_3}...p_k^{b_k} $
$ (a, b) = p_1^{min(a_1, b_1)}p_2^{min(a_2, b_2)}p_3^{min(a_3, b_3)}...p_k^{min(a_k, b_k)} $
例题
[CF 664A] Complicated GCD
[CF 757B] Bash’s Big Day
欧几里得算法
作用
又称辗转相除法, 迭代求两数 (gcd) 的做法
公式
(gcd(a, b) = gcd(b, a \% b))
code
递归写法
int gcd(int a, int b) { return !b ? a : gcd(b, a % b);}
二进制优化
inline int gcd(int x, int y) {
int i, j;
if (x == 0) return y;
if (y == 0) return x;
for (i = 0;0 == (x&1); ++i) x >>= 1;
for (j = 0;0 == (y&1); ++j) y >>= 1;
if(j<i) i = j;
while (1) {
if (x < y) x ^= y , y ^= x , x ^= y;
if (0 == (x -= y)) return y << i;
while (0 == (x & 1)) x >>= 1;
}
}
裴蜀定理
定义
设 ((a, b) = d), 则对于任意整数 (x, y), 有 (d | (ax + by)) 成立;
特别地, 一定存在 (x, y) 满足 (ax + by = d).
等价的表述:不定方程 (ax + by = c (a, b, c) 为整数 ()) 有解的充要条件为 ((a, b) | c)
推论
(a,b) 互质等价于 (ax + by = 1) 有解
扩展欧几里得
定义
就是如何求得 (ax + by = d) 的一个解, (d = (a, b))
做法
考虑使用欧几里得算法的思想, 令 (a = bq + r), 其中 (r = a mod b)
递归求出 (bx + ry = d) 的一个解
设求出 (bx + ry = d) 的一个解为 (x = x_0, y = y_0)
将 (a = bq + r) 带入 (ax + by = d) 得
(b(qx + y) + rx = d)
令 (qx+y = x_0, x = y_0), 则上式成立
故 (x = y_0, y = x_0 - qy_0) 为 (ax + by = d) 的解
递归的边界: (b = 0) 时, 令 (x = 1, y = 0).
code
void exgcd(int a, int b, int &x, int &y) {
if (b == 0) {
x = 1;
y = 0;
return ;
}
int q = a / b, r = a % b;
exgcd(b, r, y, x);
y -= q * x;
}
求得所有解
先用 (exgcd) 求出任意一个解 (x = x_0, y = y_0)
再求出 (ax + by = 0) 的最小的解
(x = d_x = dfrac{b}{(a, b)}, y = d_y = -dfrac{a}{(a, b)})
所有解就是 (x = x_0 + kd_x, y = y_0 + kd_y, k in Z)
逆元
定义
若 (ax equiv 1 pmod b) , 则称 (x) 是 (a) 关于模 (b) 的逆元.
常记做 (a^{-1})
同时, 上式等价于 (ax + by = 1) (同余的性质)
条件
逆元不一定存在, 存在的充要条件是 ((a, b) = 1)
推论
(p) 是质数, (p) 不整除 (a), 则 (a) 模 (p) 的逆元存在
结论
在 ([0, b)) 的范围内, (a) 关于模 (b) 的逆元(若存在), 是唯一的.
方法
可以用 (exgcd) 求逆元
code
int inv(int a, int b) {
int x, y;
exgcd(a, b, x, y);
return x;
}
线性求逆元
方法一
递推
假设现在要求 (i) 的逆元
考虑带余除法, 设 (p = iq + r), 则有 (iq + r equiv 0 pmod p)
考虑到 (p) 是质数, 因此 (r) 不为 (0), (r) 的逆元存在
等式两边乘 (i^{-1} + r^{-1} equiv 0 pmod p)
因此 (i^{-1} equiv -qr^{-1} equiv -lfloordfrac{p}{i}
floor(p mod i)^{-1} pmod p)
code
inline int inv(int n) {
inv[1] = 1;
for (int i = 2; i <= n; i++ ){
inv[i] = (p - p / i)*inv[p % i] % p;
}
}
方法二
倒推
先求 (n!) 的逆元((exgcd) 或者之后会提到的快速幂)
然后利用 (((k - 1)!)^{-1} equiv k imes (k!) ^{-1} pmod p)
倒推求出 (1!...n!) 的逆元
再利用 (k^{-1} equiv (k - 1)! imes (k!)^{-1} pmod p)
就可以求出 (1...n) 的逆元了
code
不想写其实是我没用过,一直用的递推
费马小定理
定义
(a^{p - 1} equiv 1 pmod p)
变式: $a^{p - 2} equiv dfrac{1}{a} pmod p Leftrightarrow a imes a^{p - 2} equiv 1 pmod p $
前提
(p) 是质数, 且 (a) 不是 (p)的质数
方法
直接快速幂取模就行
code
inline ll f_pow(ll x, ll y, int mod) {
ll ans = 1;
while (y) {
if (y & 1) ans = (ans * x) % mod;
x = (x * x) % mod;
y >>= 1;
}
return ans;
}
inline int fermat(int a, int mod) {
return f_pow(a, mod - 2);
}
线性同余方程
定义
形如 (ax equiv c pmod b) 的方程称为线性同余方程
等价于 (ax + by = c) 因此有解条件为 ((a, b) mid c)
求解
任意的线性同余方程总可以判定为无解,或化为 (x equiv a pmod m) 的形式
线性同余方程组 && 中国剩余定理 && 欧拉定理
不想写了,之后再写,先挂一个大佬的链接吧
大佬