简单数论
质约数
判断质数 $O(\sqrt{n})$
1 | bool isPrime(int x) |
分解质因数 $O(\log{n}) O(\sqrt{n})$
最多只包含一个大于 $\sqrt{n}$ 的 质因数
1 | void divide(int n) |
筛质数
埃筛
找出小于等于 $n$ 的质数
$O(n\log{\log{n}})$
1 | void get_prime(int n) |
- 线筛 $O(n)$
1 | void get_prime(int n) |
求约数
1 | vector<int> get_div(int n) |
约数个数
对于一个正整数$n$，它的约数个数可以通过以下步骤来计算：
- 将$n$分解质因数，得到形如$n = p_1^{\alpha_1} \cdot p_2^{\alpha_2} \cdot … \cdot p_k^{\alpha_k}$的表达式，其中$p_i$为质数，$\alpha_k$为对应的指数。
- 约数个数即为:
$$\prod_{i=1}^{k} (1 + \alpha_i)=(1 + \alpha_1) \cdot (1 + \alpha_2) \cdot … \cdot (1 + \alpha_k)$$
例如，对于$n = 12$，它的约数为1、2、3、4、6、12，共有6个约数。我们可以将12分解为$12 = 2^2 \cdot 3^1$，然后计算约数个数为$\prod_{i=1}^{2} (\alpha_i + 1) = (1 + 2) \cdot (1 + 1) = 3 \cdot 2 = 6$。
int 范围内一个数字的约数最多约1500个
可以用哈希表存
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20cin>>x;
for(int i=2;i<=x/i;i++) //求 x 的分解质因数,存到 map 里面
{
if(x%i==0)
{
while (x%i==0)
{
x=x/i;
primes[i]++;
}
}
}
if(x>1) primes[x]++;
ll ans=1;
for(auto prime:primes)
{
ans=ans*(prime.second+1)%mod;
}
约数之和
假设正整数 $n$ 的质因数分解为：$n = p_1^{\alpha_1} \cdot p_2^{\alpha_2} \cdot … \cdot p_k^{\alpha_k}$
那么 $n$ 的所有约数之和可以表示为：
$$\sigma(n) = (1 + p_1 + p_1^2 + … + p_1^{\alpha_1})\cdot (1 + p_2 + p_2^2 + … + p_2^{\alpha_2}) \cdot … \cdot (1 + p_k + p_k^2 + … + p_k^{\alpha_k})$$
1 | cin>>x; |
最大公约数
1 | int gcd(int a,int b) |
欧拉函数
欧拉函数表示 1~$n$ 中互质的数的个数
（互质是公约数只有1的两个整数）$n$ 的质因数分解： (n = p_1^{\alpha_1} \cdot p_2^{\alpha_2} \cdot … \cdot p_k^{\alpha_k})
$n$ 的欧拉函数 (\phi(n)) 可以用以下公式表示：
$$\phi(n) = n \times \left(1 - \frac{1}{p_1}\right) \times \left(1 - \frac{1}{p_2}\right) \times \ldots \times \left(1 - \frac{1}{p_k}\right)$$
1 | void get(int n) //求n的欧拉函数 |
或 线筛求欧拉函数 (可用来求 连续 数字的欧拉函数)
1 | void euler(int n) //欧拉 |
快速幂
1 | ll qmi(int a,int k,int mod) //快速计算a^k%mod |
快速幂求逆元
推导过程：
如果p是一个素数，而a是不是p的倍数的整数，则有费马小定理：
$$a^{p-1} \equiv 1 \ (\text{mod} \ p)$$
我们要找到一个数 “x”，满足以下条件：
$$a \cdot x \equiv 1 \ (\text{mod} \ m)$$
步骤1：计算 $a^{m-2} \ (\text{mod} \ m)$
我们将 “a” 的幂乘以 $m-2$ 并将结果对 “m” 取模。这基于费马小定理，该定理指出，如果 “a” 和 “m” 互质（gcd(a, m) = 1），那么 $a^{m-1} \equiv 1 \ (\text{mod} \ m)$。将同余式的两边都乘以 $a^{-1}$，我们得到 $a^{m-2} \equiv a^{-1} \ (\text{mod} \ m)$。步骤2：令 $x = a^{m-2} \ (\text{mod} \ m)$
步骤1的结果给出了我们所需的模意义下的乘法逆元 “x”。
因此，模意义下的乘法逆元公式为：
$$a^{-1} \equiv a^{m-2} \ (\text{mod} \ m)$$
注意特判，即 $a=m$ 时无解且本公式只在 $q$ 为质数的时候成立
1 | ll qmi(int a,int mod-2,int mod) |
扩展欧几里得
裴蜀定理：
$$ax + by = \text{gcd}(a, b)$$
exgcd(a, b, x, y) = exgcd(b, a % b, y, x)
$$b \times y + (a - \lfloor \frac{a}{b} \rfloor \times b) \times x = d$$
$$b \times (y - \lfloor \frac{a}{b} \rfloor \times x) + a \times x = d$$
∴ 更新 y 为 (y - \lfloor \frac{a}{b} \rfloor \times x)
1 | int exgcd(int a,int b,int &x,int &y) |
线性同余方程
$ax \equiv b \pmod{m}$
利用拓展欧几里得算法求解
$ax≡b\pmod{m} \Rightarrow ax+my≡b\pmod{m}$仅$b=kd$ 时候有解$(d=gcd(a,m))$，代入得
$$a(\frac{x}{k})+m(\frac{y}{k})=b$$通过exgcd可算出 $(\frac{x}{k})$ 的值$=x’$，则$x=k*x’$
线性求逆元
求 1~p 之间所有数关于 $\pmod{p}$ 的逆元
1 | insum[1]=1; |
高斯消元
线性代数：增广矩阵化简为最简阶梯矩阵….
1 |
|
组合数
- 组合数公式:
$$C_{a}^{b} = \frac{a!}{b! \cdot (a - b)!}=C_{a-1}^{b}+C_{a-1}^{b-1}$$
递归
$C_{a}^{b}=C(a,b)=C(a-1,b-1)+C(a-1,b)$
$N \approx 2000$
1 | void init() |
预处理
- $N \approx 10^5$
fac[i] 为 $i$ 的阶乘， infac[i] 为 $i$ 阶乘的逆元
$$C_{a}^{b} = \frac{a!}{b! \cdot (a - b)!}=fac[a]*infac[b]*infac[a-b]$$
1 | ll qmi(int a,int k,int q) //用来算逆元 |
Lucas 卢卡斯定理
- $N \approx 10^{18} $
$$C_{a}^{b} \equiv C_{a\pmod{p}}^{b\pmod{p}}*C_\frac{b}{p}^\frac{a}{p}\pmod{p}$$
1 |
|
高精度 （待补）
1 | //``` |
卡特兰数
合法路径数：
$$C_{2n}^{n} - C_{2n}^{n-1} = \frac{(2n)!}{n! \times n!} - \frac{(2n)!}{(n+1)!\times(n-1)!} $$
$$= \frac{(2n)! \times (n+1)}{n!\times (n+1)!}- \frac{(2n)! \times n}{n!\times (n+1)!}$$
$$= \frac{(2n)!}{n! \times (n+1)!} =\frac{1 }{n+1}\times \frac{(2n)! }{(n)!\times(n)!}$$
$$=\frac{C_{2n}^{n} }{n+1}$$
容斥
$|A_1 \cup A_2 \cup \ldots \cup A_n| = \sum_{i=1}^{n} |A_i| - \sum_{1 \leq i < j \leq n} |A_i \cap A_j| + \sum_{1 \leq i < j < k \leq n} |A_i \cap A_j \cap A_k| - \ldots + (-1)^{n-1} |A_1 \cap A_2 \cap \ldots \cap A_n|$
例：计算 1~n 中能被质数数组 p[] 中某个（些）元素整除的数的个数
1 |
|
Nim 游戏
$S_i$ 表示第 $i$ 堆石头数量（$\bigoplus$：异或）
先手必胜：$S_1\bigoplus S_2\bigoplus S_3\bigoplus S_4······S_n≠0$
先手必败：$S_1\bigoplus S_2\bigoplus S_3\bigoplus S_4······S_n=0$
注：任何数和0异或都等于原数
SG 函数
定义 $mex(S)$ 为求出不属于集合 $S$ 的最小非负整数的运算，即：$mex(S)=min[x]$, 其中 $x$ 属于自然数，且 $x$ 不属于集合 $S$
（结束为0）
对于一个有向图 $D$：
先手必胜：$S(D)≠0$ （必有一条路可以走到$S(D)=0$）
先手必败：$S(D)=0$
对于 $n$ 个有向图D：
先手必胜：$S(D_1)\bigoplus S(D_2)\bigoplus S(D_3)\bigoplus ······S(D_n)\bigoplus ≠0$
先手必败：$S(D_1)\bigoplus S(D_2)\bigoplus S(D_3)\bigoplus ······S(D_n)\bigoplus =0$
1 |
|