简介
终于要开始数学了吗？
素数筛
欧拉筛
在欧拉筛中我们保证每个合数一定是被它最小的素因子给筛掉，所以时间复杂度为 $O(n)$
证明好像很显然，大概就是我们在第二层循环所要筛的 $i\cdot pri[j]$，如果 $i\bmod pri[j]=0$ 则说明，对于以后的 $i\cdot pri[k]$ 来说，它至少有一个素因子 $pri[j]$，且 $pri[j]<pri[k]$
时间复杂度 $O(n)$
1 | bool isp[maxn]; int pri[maxn], cnt; |
Eratosthenes 筛
这东西也叫埃氏筛
大概就是用所有小于 $\sqrt n$ 的素数的倍数去筛，时间复杂度为 $O(n\log \log n)$
有一个小优化，对每个素数 $p$，我们从 $p^2$ 开始筛，因为对于 $2p,3p,…,(p-1)p$ 都已经被更小的 $p$ 筛过了
1 | bool isp[maxn]; int pri[maxn], cnt; |
区间筛
大概就是要筛 $[l,r]$ 内的素数，$r$ 的数量级很大，在 $10\times 10^{13}$ 以上，但是 $r-l+1\le 10^6$，这个时候我们可以提前筛好 $\sqrt r$ 内的素数，然后用这些素数再去筛 $[l,r]$，时间复杂度 $O(\sqrt r \log r)$
1 | int pri[maxn], cnt; bool isp[maxn]; |
最大公约数
最大公约数，又称为 $gcd$，以下在不产生歧义的情况下可能会用使用 $()$ 表示最大公约数，$[]$ 表示最大公倍数
定理 1：$gcd(a,b)$ 是 $a$ 和 $b$ 的线性组合中最小的正整数
证明：令 $g=gcd(a,b)$，$s$ 为 $a$ 和 $b$ 的线性组合中最小的正整数
$g|a,g|b$，所以 $g|(ax+by)$，所以 $g|s$，又因为 $g>0,s>0$，所以 $g\le s$
令 $q=\lfloor\frac{a}{s}\rfloor$，我们得到 $r=a\bmod s=a-qs=a-q(ax+by)=a(1-qx)+b(-qy)$
也就是说 $r$ 也是 $a$ 和 $b$ 的一个线性组合，由于 $0\le r<s$，所以 $r=0$，所以有 $s|a$，同理有 $s|b$
所以 $s|g$，又因为 $s>0,g>0$，所以 $s\le g$
综上可得 $s=g$
定理 2：$gcd(ax, bx) = xgcd(a, b)$
证明：显然
定理 3：$gcd(a, b) = gcd(a - b, b)$
证明：
令 $a = n_1gcd(a,b),b=n_2gcd(a,b)$，相减显然不影响结果
同理，多个数的 $gcd$ 也可以进行类似操作
定理 4：$gcd(a, b) = gcd(b,a \bmod b) $
证明：
定理 5：$gcd(a, b) \times lcm(a, b) = ab$
证明：
令 $g=gcd(a,b),l=lcm(a,b),a=x\cdot g,b=y\cdot g$
$lcm(a,b)=lcm(x\cdot g,y\cdot g)=g\cdot lcm(x,y)=g\cdot x\cdot y\Rightarrow gcd(a,b)\cdot lcm(a,b)=g\cdot x\cdot g\cdot y=a\cdot b$
定理 6：$gcd(a^n-1,a^m-1)=a^{gcd(n,m)}-1$
证明：
$(a^n-1,a^m-1)=(a^n-a^m,a^m-1)=(a^m(a^{n-m}-1),a^m-1)$
显然 $a^m$ 和 $a^m-1$ 互质
所以我们得到 $(a^{n-m}-1,a^m-1)$，也就是说我们可以对指数做辗转相除
所以最后一定能得到 $a^{(n,m)}-1$
定理 7：$lcm(a_1,a_2,…a_n)=\frac{1元gcd之积\times 3元gcd之积\cdots}{2元gcd之积\times 4元gcd之积\cdots }$
首先 $lcm$ 肯定可以对于每个素因子单独考虑
我们现在仅考虑素数 $p_i$，不妨设 $b_i$ 为 $a_i$ 素因子分解之后 $p_i$ 的指数
注意到 $p$ 的贡献为 $max(b_1,b_2,\cdots,b_n)$
这个 $max$ 可以看做是全集的 $max$，那么我们直接套 $max-min$ 容斥，就能得到上述式子
欧几里得算法
大概就是利用 $gcd(a,b)=gcd(b,a\bmod b)$
时间复杂度为 $O(\log n)$
证明：
用 $a_0$ 和 $a_1$ 表示初始的两个数。
数列 $a_i = a_{i-2} \mod a_{i-1}$ 直到 $a_k = 0$，最大公约数即为 $a_{k-1}$
可以发现 $a_i\leq a_{i-2} / 2$，也就是说，每两个数减小至少一半，所以复杂度是 $O(\log n)$
证明：
分情况讨论：
若 $a_{i-1}\leq a_{i-2}/2$ ，则 $a_{i}\leq a_{i-2} / 2$
否则 $a_{i-1}>a_{i-2} / 2$，则 $a_{i} = a_{i-2}-a_{i-1}$，则 $a_i\leq a_{i-2} / 2$
1 | int gcd(int a, int b) { return b == 0 ? a : gcd(b, a % b); } |
扩展欧几里得算法
首先这东西是用来求解 $a\cdot x+b\cdot y=(a,b)$ 的一对整数解 $(x,y)$
另外关于我们求的是任意一堆整数解，有的时候我们需要是 $x$ 为最小正整数一类的限制，这时候我们需要考虑如何对 $x$ 或 $y$ 进行变换
$a(x+k\alpha)+b(y-k\beta)=(a,b)$
我们考虑如何使得 $\alpha$ 和 $\beta$ 最小，容易发现当 $\alpha = \frac{[a,b]}{a}$ 最小
大概的思路就是利用欧几里得算法的递归过程，维护 $x$ 和 $y$ 的值，因为在欧几里得算法底层可以直接得到 $(1,0)$ 这组解
我们思考下如何递归维护 $x$ 和 $y$
首先我们有 $a\cdot x_1+b\cdot y_1=(a,b)$ 和 $b\cdot x_2+(a\bmod b)y_2=(b,a\bmod b)$
可以推出 $a\cdot x_1+b\cdot y_1=b\cdot x_2+(a\bmod b)y_2$
右边或化简一下得到 $a\cdot x_1+b\cdot y_1=a\cdot y_2+b(x_2-\lfloor\frac{a}{b}\rfloor y_2)$
这样就得到了两层之间 $x$ 和 $y$ 的关系
1 | void exgcd(int a, int b, int &x, int &y) { |
求 $(x,y)$ 的正整数解个数，$x$ 的最小正整数解，$y$ 的最小正整数解，$x$ 的最大正整数解，$y$ 的最大正整数解， 保证 $a,b,c$ 都为正整数
1 | void work() { |
费马小定理和威尔逊定理
威尔逊定理
一个大于 $1$ 的正整数 $p$ 为素数的充要条件是，$(p-1)!\equiv -1(\bmod p)$
费马定理
对于任意素数 $p$ 和任意非 $p$ 倍数的整数 $a$，一定有 $a^{p-1}\equiv 1(\bmod p)$
同余
$ab\equiv ac(\bmod m)\Rightarrow b\equiv c(\bmod \frac{m}{(m,a)})$
$a\equiv b(\bmod km)\Rightarrow a\equiv b(\bmod m)$
中国剩余定理
这里保证 $m_i$ 两两互质，求 $x$ 的最小正整数解
令 $T=\prod_{i=1}^nm_i,M_i=\frac{T}{m_i},M_it_i\equiv 1(\bmod m_i)$，那么我们能够构造出一个解 $x_0=\sum_{i=1}^na_iM_it_i$，任意解 $x=x_0+kM$
1 | ll a[maxn], m[maxn], M[maxn], inv[maxn]; |
扩展中国剩余定理
实际上与中国剩余定理并没有什么关系，基本的思想就是每次将两个方程合并成一个方程，然后依次合并到只剩一个方程，那么我们先从两个方程看起
注意到 $x$ 在 $[0,[m_1,m_2]-1]$ 内只有一个解，所以在 $(m_1,m_2)$ 整除 $(a_1,a_2)$ 的情况下，根据裴蜀定理一定能求出一个解 $x\equiv x_0(\bmod [m_1,m_2])$，然后我们依次合并两个方程即可
1 | ll a[maxn], m[maxn]; |
剩余系
剩余类
我们将模 $m$ 相等的数划为一类，那么这一类就叫做模 $m$ 的一个剩余类
完全剩余系
我们从模 $m$ 的 $m$ 个剩余类中分别抽出一个数，这 $m$ 个整数就叫做模 $m$ 的一个完全剩余系
性质：
- 令 $\lbrace a_i\rbrace$ 为模 $m$ 的一个完全剩余系，则 $\lbrace a_i+b\rbrace$ 同样为模 $m$ 的一个完全剩余系
- 令 $\lbrace a_i\rbrace$ 为模 $m$ 的一个完全剩余系，$(k,m) = 1$，则 $\lbrace ka_i\rbrace$ 同样为模 $m$ 的一个完全剩余系
- 令 $\lbrace a_i\rbrace$ 为模 $m$ 的一个完全剩余系，$(k,m) = 1$，则 $\lbrace ka_i+b\rbrace$ 同样为模 $m$ 的一个完全剩余系
简化剩余系
模 $m$ 的缩系为 $\{a_i\}$，$0<a_i<m$，且 $gcd(m, a_i)=1$，这样的 $a_i$ 有 $\varphi(m)$ 个
性质：
- 令 $\lbrace a_i\rbrace$ 为模 $m$ 的一个简化剩余系，$(k,m) = 1$，则 $\lbrace ka_i\rbrace$ 同样为模 $m$ 的一个完全剩余系
阶和原根
阶
若 $a,m$ 为正整数，且 $(a,m)=1$，我们称满足 $a^r\equiv 1(\bmod m)$ 的最小正整数 $r$ 为 $a$ 模 $m$ 的阶，记作 $\delta_m(a)$
- $\delta_m(a)|\varphi(m)$
- 令 $\delta_m(a)=k$，则 $a^0,a^1,\cdots,a^{k-1}$ 模 $p$ 两两不同余
- 若 $ab\equiv 1(\bmod m)$，则 $\delta_m(a)=\delta_m(b)$
- $\delta_m(a^k)=\frac{\delta_m(a)}{gcd(\delta_m(a),k)}$
原根
若 $a,p$ 为正整数，且 $(a,p)=1$，称满足 $\delta_p(a)=\varphi(p)$ 的 $a$ 为模 $p$ 的一个原根
- $2,4,p^k,2\times p^k$，其中 $p$ 为奇素数，$k$ 为正整数，只有这样的数才有原根
- 设 $p\ge 3$，$(g,p)=1$，$g$ 为模 $p$ 的原根的充要条件是，则对于任意 $\varphi(p)$ 的素因子 $p_i$，必有 $g^{\frac{\varphi(p)}{p_i}}\not\equiv1 $
- 若 $n$ 存在原根，则其原根个数为 $\varphi(\varphi(p))$
- 若 $n$ 存在原根，则其最小原根的大小为 $n^\frac{1}{4}$
- 若 $n$ 存在原根，且其最小原根为 $g$，则 $t=g^k$ 为 $n$ 的原根的充要条件是 $(k,\varphi(n))=1$
1 | int get_mnrt(int n) { // 求最小原根 |
BSGS
就是用来求解同余方程 $a^x\equiv b(\bmod p)$ 的解，需要保证 $(a,p)=1$
我们令 $q=\lceil\sqrt p\rceil$，则 $x$ 一定能够拆成 $A\times q-B$，其中 $A\in[1,q],B\in[0,q]$
所以我们将 $b\times a^B$ 存到 $hash$ 表或 $map$ 中，然后枚举 $A$ 求解即可，时间复杂度 $O(\sqrt p)$
1 | unordered_map<int, int> mp; |
exbsgs
求解同余方程 $a^x\equiv b(\bmod p)$ 的解，不保证 $(a,p)=1$
1 | int bsgs(int p, int a, int b, int _mul) { |
逆元
简介
定义：对于正整数 $a $ 和 $m$，如果有 $ax\equiv 1(\bmod m)$，并且 $(a,m)=1$，则把这个同余方程中 $x$ 的最小正整数解叫做 $ a \bmod m$ 的逆元
逆元最经典的用法就是在求解除法取模 $\frac{a}{b}\bmod m$ 时，因为除法无法取模，所以我们只能让 $a$ 乘上 $b$ 的逆元
当然该式在 $b|a$ 时有一个特殊求法，$\frac{a}{b}\bmod m=\frac{(a\bmod bm)}{b}$
注意到对于 $a$ 和模数 $m$，当且仅当 $(a,m)=1$ 时，$a$ 在模 $m$ 意义下才有逆元
费马小定理
定义：$p$ 为素数，$a$ 为任意自然数，我们都有 $a^p\equiv a(\bmod p)$
化简一下得到 $a^{p-1}\equiv 1(\bmod p)$
1 | ll pow_mod(ll x, ll n) { |
扩展欧几里得算法
对于 $a\cdot x\equiv 1(\bmod m)$，可以化为 $a\cdot x+m\cdot y=1$
$x$ 可以直接拿扩欧求
线性求逆元
$O(n)$ 求 $[1,n]$ 模 $p$ 的逆元
我们令 $p=ki+r$，其中 $k=\lfloor \frac{p}{i}\rfloor,r=p\bmod i$
$r<i$，所以可以递推
1 | ll inv[maxn]; |
例题
给定 $n(n\le 10^5)$，求 $[1,2,\cdots,n-1]$ 的最长子序列，使得这个子序列所有元素的乘积模 $n$ 等于 $1$
扩展欧拉定理
$\begin{equation}~a^c~\equiv~\left\{
\begin{array}\\
a^{c \bmod \varphi(m)} &\gcd(a,m)~=~1 \\
a^c &\gcd(a,m)~\neq~1~\and~c~<~\phi(m) \\
a^{c\bmod \varphi(m)~+~\varphi(m)} & \gcd(a,m)~\neq~1~\and~c~\geq~\phi(m)
\end{array}
\right.
\end{equation}$
证明：
Pollard-Rho 和 Miller Rabin
复杂度大概是几倍 $n^{\frac{1}{4}}$
1 | bool isp(ll n) { |
基于值域预处理的快速 GCD 算法
设 $v$ 为值域，则预处理为 $O(v)$，查询 $O(1)$
对于每个数 $x$，我们将其变成 $x=a\times b\times c$ 的表示方法，满足 $a\le b\le c$ 且满足 $a,b,c\le \sqrt x$ 或 $a,b,c\in Prime$
根据某些神奇的性质，我们可以使用线性筛来预处理每个数的这种表示方法，同时预处理 $O(\sqrt v)$ 之内任意两个数的 $gcd$，然后对于每次查询 $gcd(x,y)$，我们只需要将 $x$ 和 $y$ 按照表示方法分解后求 $gcd$ 即可
1 | namespace Gcd { |
一些性质
- $n$ 不是集合 $S$ 中任何一个数的倍数等价于 $n$ 对 $S$ 的 $lcm$ 取模后不是 $S$ 中任何一个数的倍数
- 不超过 $n$ 的与 $n$ 互质的数的乘积对 $n$ 取模只能为 $1$ 或者 $-1$
例题
简要题意：有 $T$ 组询问，每次给定 $n$ 和 $k$，求 $[1,n]$ 中有多少数不被前 $k$ 个素数中任何一个素数整除
$T\le 10^5,n\le 10^{18},k\le 16$
简要题解：首先有一个经典的 $2^k$ 的容斥做法，答案即为 $(-1)^{|S|}\lfloor\frac{n}{S}\rfloor$，其中 $S$ 表示选中的集合的乘积
我们考虑将 $16$ 素数分成两半，前 $8$ 个素数的乘积为 $9699690$，根据数论知识，我们知道 $n$ 不是集合 $S$ 中任何一个数的倍数等价于 $n$ 对 $S$ 的 $lcm$ 取模后不是任何一个数的倍数
那么 $[1,n]$ 的答案为 $f[9699690]\times \lfloor\frac{n}{9699690}\rfloor+f[n\bmod 9699690]$，其中 $f[i]$ 表示 $[1,i]$ 的答案，$i\in[1,9699690]$
对于后半的素数，我们直接做容斥，对于一个集合 $S$，能够得到是 $S$ 的倍数的数为 $S,2S,\cdots,\lfloor\frac{n}{S}\rfloor S$，我们再将 $1$ 到 $\lfloor\frac{n}{S}\rfloor$ 是前 $8$ 个素数的倍数数给剔除即可，时间复杂度 $O(\sum_{i=1}^8\frac{9699690}{p_i}+T2^8)$
简要题意：有 $T$ 组数据，给定一个长度为 $n$ 的序列 $a_i$，$m$ 次询问 $[a_l,a_{l+1},\cdots,a_r]$，答案对 $10^9+7$ 取模
$n,m,T\le 300,a_i\le 2^{60}$
简要题解：我们令 $[a_1,a_2,\cdots,a_{n-1}]=\prod_{i=1}^{n-1}b_i$，那么我们现在只需要求 $([a_1,a_2,\cdots,a_{n-1}],a_n)$
这个东西就是 $(\prod_{i=1}^{n-1}b_i,a_n)$，这个东西显然可以在乘的时候对 $a_n$ 取模
那么 $b_n$ 就等于 $\frac{a_n}{(\prod_{i=1}^{n-1}b_i,a_n)}$，实际上就是把多余的给除掉，时间复杂度 $O(Tn^3)$，可以通过分治优化到 $O(Tn^2\log n)$
简要题意：给定一个素数 $p$ 以及一个长度为 $p-1$ 的序列 $a_i$，求是否能从序列 $a_i$ 中选出若干个数，使得它们的乘积模 $p$ 等于 $1$
$p\le 10^5$
简要题解：我们考虑求出 $p$ 的原根 $g$，然后我们将 $a_i$ 变成一个范围为 $[0,p-2]$ 的数，问题被转换成是否能选出若干个数出来使得它们的和是 $p-1$ 的倍数，我们可以直接上 $bitset$，时间复杂度 $O(\frac{p^2}{64})$
National Taiwan University NCPC Preliminary 2021 E Identity Subset
简要题意：给定一个整数 $n$，保证 $n$ 是奇质数 $p$ 的正整数次方，现在有 $m$ 次询问，每次询问给定两个正整数 $x,y$，保证 $(x,n)=1,(y,n)=1$，问是否存在非负整数 $a$，使得 $x^a\equiv y(\bmod n)$
$x,y<n\le 10^{18},m\le 2\times 10^4$
简要题解：因为保证 $n$ 是奇质数的正整数次方，所以 $n$ 一定存在原根 $g$ 和非负整数 $s,t$，使得 $x\equiv g^s(\bmod n),y\equiv g^t(\bmod n)$，那么询问变为是否存在非负整数 $a$，使得 $sa\equiv t(\bmod \varphi(n))$，该式有解当且仅当 $(s,\varphi(n))|t$，即 $(s,\varphi(n))|(t,\varphi(n))$
根据阶的性质，我们有 $\delta_n(g^k)=\frac{\delta_n(g)}{(\delta_n(g),k)}$，所以如果存在非负整数 $a$，则一定有 $\delta_n(y)|\delta_n(x)$，至于如何验证这个东西，我们一定有 $\delta_n(y)|\varphi(n)$，所以我们考虑对于首先对于 $\varphi(n)$ 分解质因数，然后通过不断试除来得到 $\delta_n(x)$，然后通过验证 $y^{\delta_n(x)}$ 是否同余 $1$ 即可
时间复杂度 $O(nm^{\frac{1}{4}})$