数论
整除 : a | b \ : b 被 a 整除
质数 :只被 1 和 本身整除的数
最大公因数 (gcd):
- 求法 : 辗转相减法(O(n))， 辗转相除法(O())
辗转相除法 : gcd(a, b) = gcd(b, a\mod b)
int gcd(int a, int b){
if(b == 0) return a;
return gcd(b, a % b);
}
int gcd(int a, int b){
return !b ? a : gcd(b, a % b);
}
(在 C++ 11 及以上 提供了 __gcd() )
最小公倍数 : lcm(a, b) = \frac{a \times b}{gcd(a, b)}
分解质因数 : 把一个数分为若干个质数的乘积
- 求法 :
暴力枚举 : O(n)
显然, 可优化为 O(\sqrt{n})
筛法
- 埃氏筛 : 枚举每个数, 将其所有倍数筛去;O(n \ln n)
优化 : 只筛质数的倍数 O(n \log \log n)
- 欧拉筛 : 只让每一个质数被其最小质因子筛去 O(n)
for(int i = 2; i <= n; ++i){
if(!vis[i]) p[++cnt] = i;
for(int j = 1; i * p[j] <= n; ++j){
vis[i * p[j]] = 1;
if(i % p[j] == 0) break;
}
}
eg1 : 有 n 个点, 第 i 个点到第 j 个点有边当且仅当 j 是 i 的倍数且 \frac{j}{i} 为质数 (单向边)， 询问从点$1$ 到点 x 的方案数
eg2 : P1621 集合
solution :
考虑枚举 p , 用并查集维护
eg3 : P1069 [NOIP2009 普及组] 细胞分裂
取模 \mod {}
通常 \frac{a}{b} \mod c 不等于 \frac{a \mod c}{b \mod c} \mod c
同余 \equiv
如果 a \equiv b \ (mod \ c) , 且 \gcd(a, b, c) = k, 则 \frac{a}{k} \equiv \frac{b}{k} \ (mod \ \frac{c}{k})
如果 a \equiv b \ (mod \ c) , k | c,则 a \equiv b \ (mod \ k)
逆元 :
方程 ax \equiv 1 (mod \ p) 的解 x_0 , 记为 x_0 = a^{-1}
存在条件 \gcd(a, p) = 1
- 求法 :
单个 :
- 快速幂(欧拉定理, 费马小定理)
- exgcd
多个 ;
- 线性筛
- 线性递推
inv[i] = b - b / j * inv[b % i];
费马小定理
$$ a^{p - 1} \equiv 1 (mod \ p)$$
$$a \times a ^{p - 2} \equiv 1 (mod \ p) $$
( p 为质数)
eg4 : Magic Five
小组成员 : 邵品渊，邵品砚，蒋佳成，顾天泽，马天翔，陈继禹