零.前言
组合意义天地生，代数推导jzy。
一.Miller-Rabin素性测试
Miller-Rabin-Miller-Rabin-Mikuer-Robin-Milker-Rocky-Morty-Rick。
费马素性测试
费马曾言道：“\(a^{p-1} \equiv 1 \pmod p\) ，当 \(p\) 是质数时。”因此，可以随机 \(a\) 来进行关于 \(p\) 的素性测试。但是，费马小定理的逆定理是假的，并且存在 Carmichael 数满足 \(p\) 是合数并且能通过对于所有 \((a,p) = 1\) 的 \(a\) 的费马素性测试。
二次探测定理
\(x^2 \equiv 1 \pmod p\) 的解为 \(x_1=1,x_2=p-1\)，当 \(p\) 为奇质数时。可以移项加因式分解，如果想证明这个定理。根据高次剩余也能得出解是这两个，当然。
Miller-Rabin素性测试
不知道为什么，Carmichael 数一定不是 \(p^k(k>1)\) 的形式。这就导致如果使用二次探测定理，Carmichael 数的二次剩余不会只有两个解。
待补。
二.Pollard-Rho 质因数分解
对 \(n\) 进行质因数分解，\(n \leq 10^{18}\)。
如果我们可以找到 \(n\) 的一个非平凡因子，在一个合适的复杂度内，结合上 Miller-Rabin 当然就可以做到质因数分解。现在的问题就是怎么找到一个非平凡因子，Pollard-Rho 算法就是用来解决这个问题的。
我们首先有生日悖论，这告诉我们一个随机生成的值域在 \(1\) 到 \(V\) 的序列，第一次出现重复元素时期望长度为 \(O(\sqrt V)\)。
我们设计一个伪随机函数 \(f(x)=x^2-c\)，这个函数有两个优秀性质。一是它挺随机，二是若 \(x \equiv y \pmod p\)，则 \(f(x) \equiv f(y) \pmod p\)。你可能很疑惑，为什么突然又扯上取模了。但是其实我也很疑惑。
现在我们要努力把生日悖论和这什么东西串联在一起。你会发现，如果我们有一个不知道的非平凡因子 \(p\)，那么对于序列 \(X\)，使得 \(X_i \equiv X_j \pmod p\) 的期望长度是 \(\sqrt p\)。也就是说，我们能找到一对 \(X_i \equiv X_j \pmod p\) 的期望复杂度是 \(O(\sqrt p)\) 的，这样我们就可以以 \(O(\sqrt p)\) 的复杂度求出一个 \(d = \gcd(X_i-X_j,N)\)，\(d\) 是 \(N\) 的一个非平凡因子。
对于 \(N\)，其最大可能的最小非平凡因子也不过才只有 \(N^{\frac{1}{2}}\)，那么 \(\sqrt p\) 就只有 \(N^{\frac{1}{4}}\) 了。找到一个非平凡因子后，还得往下递归。但是会发现递归后问题数量会乘两倍，问题规模却会开平方，这东西显然是 \(N^{\frac{1}{4}}\) 收敛的（应该是吧）。
因为我们不知道 \(p\) 是多少，所以判定的条件也是 \(\gcd(X_i-X_j,N)>1\)。在模 \(p\) 意义下，这玩意相当于在一个 Rho 形上判环，所以叫 Pollard-Rho。
写的什么玩意。
三.二次剩余
解方程 \(x^2 \equiv a \pmod p\)。
考虑模数 \(p\) 为奇质数。显然可以做到 \(O(\sqrt p)\)（见四.高次剩余），但是既然 \(n=2\)，我们有特殊的好写的做法。
Legendre 符号
\(\left(\frac{a}{p}\right)\) 叫做 Legendre 符号。其值为 \(0\) 时，代表 \(a\) 是 \(p\) 的倍数，值为 \(1\) 时，代表 \(a\) 是 \(p\) 的二次剩余，值为 \(-1\) 时，代表 \(a\) 是 \(p\) 的二次非剩余。
Euler 判别式
\(\left(\frac{a}{p}\right) \equiv a^{\frac{p-1}{2}} \pmod p\)。
简洁啊。
为什么只会有 \(0,-1,1\) 三种值呢？\(0\) 比较显然不再赘述。因为由费马小定理 \(a^{p-1} \equiv 1 \pmod p\)，所以模意义开平方得 \(a^\frac{p-1}{2} \equiv \pm 1 \pmod p\)。
当 \(a\) 是 \(p\) 的倍数时，原式右边变成 \(0^{\frac{p-1}{2}}\)，成立。
否则，若存在 \(x^2 \equiv a \pmod p\)，则原式右边变成 \((x^2)^{\frac{p-1}{2}}\) 即 \(x^{p-1}\)，费马小定理得 \(1\)。不存在当然就是 \(-1\)。其实这个证明并不是特别严谨。
Cipolla 算法
又称 Pollard-Ci 算法，Ciallo 算法。
显然上面这句话是假的。
首先有个简单的东西，二次剩余的数量是 \(\frac{p-1}{2}\)，证明方法有很多，例如若 \(a^2 \equiv b^2 \pmod p\)，则 \(a \equiv \pm b \pmod p\) 所以两两配对之类的东西。
这为我们寻找一个 \(r\) 创造了条件，这个 \(r\) 要满足 \(r^2 - a\) 为二次非剩余，期望寻找（当然是随机）次数为 \(2\) 次。应该比较显然吧？
那么，我们设一个 \(c = \sqrt{r^2 - a}\)，则 \(x \equiv (r+c)^{\frac{p+1}{2}} \pmod p\) 为一个可行解。我们验证一下。
\( x^2 = (r+c)^{p+1}\\ =(r+c)^p(r+c)\\ =二项式反演!\\ =(r^p+c^p)(r+c) \)
插入：\(r^p \equiv r \pmod p\)，费马小定理可得。\(c^p \equiv {(c^2)}^{\frac{p-1}{2}}c \pmod p\)，由于 \(c^2\) 为二次非剩余，Euler 判别式得 \(c^p \equiv -c \pmod p\)。
继续！
\( =(r-c)(r+c)\\ =r^2-c^2\\ =r^2-(r^2-a)\\ =a \)
验证成功。这样我们就以 \(O(\log p)\) 的复杂度解决了二次剩余问题。（虽然要求了 \(p\) 是奇质数，但剩下的只用 CRT 合并就行了...才怪，\(2^k\) 和 \(p^k\) 都要动动脑子啊。）写代码的时候手写一个 \(c\) 类就可以了。
别忘了大多数情况下二次剩余有两个解，还有一个 \(-x\)。
四.高次剩余
考虑模数 \(p\) 为质数。
解方程 \(x^n \equiv a \pmod p\)。
非常好的一点是，\((a,p) = 1\)，避免了很多分讨。
那么那么，首先，我们有一个 \(p\) 的原根 \(g\)，这说明生活逐渐在向好的方向发展，那么原方程变为 \({(g^k)}^n \equiv g^{a'} \pmod p\)，显然 \(kn \equiv a' \pmod {p-1}\)。在新的方程里，\(n,a',p\) 已知，我们需要求解 \(k\)。
可以发现，当 \(a'\) 是 \((p-1,n)\) 的倍数时，原方程有解，设 \(d=(p-1,n)\)。首先可以解出一个解为 \(k_0=\frac{a'}{n}\)，那么通解即为 \(k0+t \times \frac{p-1}{d}\)，因为 \(\frac{p-1}{d} \times n\) 是 \(p-1\) 和 \(n\) 的最小公倍数。那么显然，解的个数即为 \(d\)。
怎么找原根？
有研究表明，对于一个数 \(n\)，如果它存在原根，那其最小原根量级为 \(O(n ^ {\frac{1}{4}})\)，也就是说支持我们去暴力找原根。
原根判定定理：设 \(m \geq 3, (g,m)=1\)，则 \(g\) 是模 \(m\) 的原根的充要条件是，对于 \(\varphi(m)\) 的每个素因数 \(p\)，都有 $ g^{\frac{\varphi(m)}{p}}\not\equiv 1\pmod m$。
假设存在 \(g'\) 满足上述条件但不是原根，那么存在 \(g'\) 的阶是 \(\varphi(m)\) 的因数但不是 \(\varphi(m)\)，那么这个阶就一定至少是一个 \(\frac{\varphi(m)}{p}\) 的因数，原因显然，与原假设矛盾，所以满足上述条件的都是原根。
同样，是原根的也一定满足上述条件。
Ex.斐波那契与循环节
非常完美的通项公式。我们设 \(x1=\frac{1+\sqrt 5}{2},x2=\frac{1-\sqrt5}{2}\)。我们还希望 \(5\) 在模 \(p\) 意义下有二次剩余，和 \(2\) 互质则更好，因为这样 \(x1\) 和 \(x2\) 都是常数，免掉了我们很多分讨。发现 \(x1x2=-1\)，待补。
五.Dirichlet 卷积
卷不动了。
事实上，高斯是狄利克雷的老师，黎曼是狄利克雷的学生。
待补。
六.Mobius 反演
反不动了。
伪证：\(d(ij) = \sum\limits_{x|i} \sum\limits_{y|i}[\gcd(x,y)=1]\)。
对于每一个 \(p^k\) 而言，必定在 \(i\) 中出现了 \(p^{k1}\)，在 \(j\) 中出现了 \(p^{k2}\)，满足 \(k1+k2=k\)。
所以当 \(\gcd(x,y)=1\) 时，\(i\) 与 \(j\) 贡献的 \(p\) 的指数只会出现 \(k1+k2+1\) 种分布情况，发现全部乘起来就是 \(\prod\limits (k_i+1)\)，即 \(d(ij)\)。
待补。（Mo biu s。）
七.亚线性筛
适用范围（函数 \(g\) 的前缀和为所求）：
杜教筛：可构造函数 \(f\)，满足 \(f\) 与 \(f * g\) 易求前缀和。
Powerful Number 筛：可构造函数 \(f\)，满足 \(f\) 是积性函数，易求前缀和且在质数点的取值与 \(g\) 相同。
Min_25 筛
并没有什么神奇构造。
Min_25 筛与质数点值
Min_25 筛被也可以叫Ex埃筛是有原因的，它的思想和埃筛的思想相似，并且可以筛质数个数。我们可以设 \(G(n,i)\) 表示前 \(i\) 个质数筛完 \(2 \sim n\) 后的答案，显然有初值 \(G(n,0) = n-1\)。
然后考虑怎么递推出 \(G(n,i)\)。第 \(i\) 轮理论上会筛掉所有最小质因子为 \(p_i\) 的合数。怎么计算筛掉数的数量？首先，因为要保证计算的数定含有质因子 \(p_i\)，可以将数全部都先除以 \(p_i\)，然后值域范围变为 \(2 \sim \lfloor \frac{n}{p_i} \rfloor\)。之后，考虑除以完之后的数的分解，发现不能含有小于 \(p_i\) 的质因子，所以答案就是 \(G(\lfloor \frac{n}{p_i} \rfloor,i-1)\)，当然，直接这么考虑还会算到并没有被筛掉的小于 \(p_i\) 的质数本身，所以还应该减去 \(i-1\)。
综上，有递推式，\(G(n,i) = G(n,i-1) - G(\lfloor \frac{n}{p_i} \rfloor,i-1) + i - 1\)。
喜闻乐见的复杂度分析要放缩啊积分啊啥的，太难了，时间复杂度估计为 \(O(\frac{n^{3/4}}{\log n})\)。
空间的话因为第一维有用的只有 \(\lfloor \frac{n}{x} \rfloor\) 这些数，当然就只有 \(O(\sqrt n)\) 个，第二维可以滚动。设 \(\sqrt n\) 以内质数个数为 \(c\)，最后答案显然为 \(G(n,c)\)。
看起来可能没什么用，但是我们可以用类似的方法筛质数和。
事实上，我们可以用 Min_25 筛筛完全积性函数的质数点值和，容易发现筛质数个数实际上是在求 \(1\) 的质数点值和，筛质数和实际上是在求 \(\operatorname{id}\) 的质数点值和。
Min_25 筛与积性函数前缀和
求 \(\sum\limits_{i=1}^{n} f(i)\)。
考虑类似做法，设 \(S(n,i)\) 表示 \(2 \sim n\) 中最小质因子大于 \(p_i\) 的所有点值之和（\(p_0 = 1\)）。需要注意的是，这里的设法和 \(G(n,i)\) 并不完全相同。可以发现，为了求质数点值，\(G(n,i)\) 故意保留了质数，而 \(S(n,i)\) 并没有保留质数。并且，因为需要的结果不同，质数点值的答案是 \(G(n,c)\)，前缀和的答案是 \(S(n,0)+f(1)\)。
暴力计算 \(S(n,i)\) 的做法和 \(G(n,i)\) 是差不多的，但是因为并没有保证完全积性，所以得带着 \(p^k(k\geq 1)\) 一起枚举。形式化地：
\(S(n,i) = \sum\limits_{j>i} \sum\limits_{k\geq 1,p^k \leq n} f(p^k)(S(\lfloor \frac{n}{p^k} \rfloor,i+1)+1)\)
等式右边的 \(S\) 中的 \(i+1\) 是为了让 \(f\) 的点值与 \(S\) 的点值互质，等式右边的 \(S\) 外的 \(+1\) 是为了计算 \(f(p^k)\)，因为 \(S\) 中并不含有 \(1\)。
容易发现，当 \(k=1\) 的时候，每个 \(p\) 都会被枚举到，所以这个暴力光第二维就是 \(O(\frac{n}{\log n})\) 的。但是实际上，对于 \(> \sqrt n\) 的 \(p_i\)，被计算的有效点值也只会有 \(p_i\) 本身，所以可以把质数单独拎出来处理。
Ex.Dirichlet 卷积
求 \(h = f * g\)。
- 当 \(f\) 与 \(g\) 中有至少一个积性函数时，可以做到 \(O(n\log \log n)\)。
怎么做呢？运用高维前缀和的思想。卷 \(1\) 可以直接枚举 \(p\) 是因为 \(1\) 是完全积性函数，但是非完全积性函数就只能连着 \(p^k(k>1)\) 一起枚举。相对的，转移顺序需要特别考虑。
另外，复杂度是不会有问题的，\(\sum\limits_{k} \lfloor \frac{n}{p^k} \rfloor\) 可以看做一个等比数列求和，所以总复杂度仍是 \(O(n\log\log n)\) 级别。
- 当 \(f\) 与 \(g\) 均为积性函数时，可以做到 \(O(n)\)。
这个就更简单了，根据积性函数与狄利克雷卷积的性质，\(h\) 一定也是积性函数，所以我们只需要卷出来 \(p^k(k\geq 1)\) 的位置的 \(h\) 值就行了，然后线性筛筛出整个 \(h\)。
那么，\(p^k\) 的部分复杂度是多少呢？随便分析一下吧。首先有 \(O(\frac{n}{\log n})\) 个质数，并且只有 \(\leq \sqrt n\) 的 \(p\) 才可能出现 \(p^k(k>1)\)，这一部分的 \(p\) 只有 \(O(\frac{\sqrt n}{\log \sqrt n})\) 也就是 \(O(\frac{\sqrt n}{\log n})\) 个，就算把 \(k\) 的上限全部看成 \(\log_2 n\) 而不是 \(\log_p n\)，\(p^k(k>1)\) 也只有 \(O(\sqrt n)\) 个。所以共有 \(O(\frac{n}{\log n})\) 个 \(p^k(k \geq 1)\)。
同样，每次卷积的复杂度看成 \(\log_2 n\)，总复杂度也只有 \(O(n)\)，而且跑不满。再加上线性筛的复杂度，总复杂度依然是 \(O(n)\)。太好了。
Ex.类欧几里得算法
先写一个推导比较复杂的。
我们有 \(f(a,b,c,n) = \sum\limits_{i=0}^n \lfloor \frac{ai+b}{c} \rfloor\)，\(g(a,b,c,n) = \sum\limits_{i=0}^n i\lfloor \frac{ai+b}{c} \rfloor\)，\(h(a,b,c,n) = \sum\limits_{i=0}^n {\lfloor \frac{ai+b}{c} \rfloor}^2\)，现在要求 \(h\)。
- 若 \(a \geq c\) 或 \(b \geq c\)。
\( h(a,b,c,d)=\sum\limits_{i=0}^n(i\lfloor \frac{a}{c} \rfloor+\lfloor \frac{b}{c}\rfloor+\lfloor \frac{(a\%c)i+(b\%c)}{c} \rfloor)^2 \\ \)
不是什么玩意，要是我真的想用 Markdown 把这玩意打出来，那我起码得杵在电脑前面一整天。虽然我本来也要杵在电脑前面一整天。
loj 模板推导。（唉。）
- 若 \(a\geq c\)。
\( \begin{aligned} \sum\limits_{x=0}^n x^{k1}{\lfloor\frac{ax+b}{c}\rfloor}^{k2} &= \sum\limits_{x=0}^n x^{k1} (\lfloor \frac{a}{c} \rfloor x+\lfloor\frac{(a\%c)x+b}{c}\rfloor)^{k2} \\ &=\sum\limits_{k=0}^{k2}C_{k2}^k {\lfloor\frac{a}{c}\rfloor}^k\sum\limits_{x=0}^n x^{k1+k} {\lfloor\frac{(a\%c)x+b}{c}\rfloor}^{k2-k} \end{aligned}\)
- 若 \(b\geq c\)。
同理可得（这里的同理指的是二项式展开与交换求和顺序）：
\(
\begin{aligned}
\sum\limits_{x=0}^n x^{k1}{\lfloor\frac{ax+b}{c}\rfloor}^{k2} &= \sum\limits_{k=0}^{k2} C_{k2}^k {\lfloor \frac{b}{c} \rfloor}^k \sum\limits_{x=0}^n x^{k1}{\lfloor \frac{ax+b\%c}{c}\rfloor}^{k2-k}
\end{aligned}\)
- 若 \(a<c\) 且 \(b<c\)。
\( \begin{aligned} \sum\limits_{x=0}^n x^{k1}{\lfloor\frac{ax+b}{c}\rfloor}^{k2} = \text{啥呀} \end{aligned} \)
nk_fzx_sd 使用了反演，效果拔群！
\( \begin{aligned} {\lfloor{\frac{ax+b}{c}}\rfloor}^{k} = \sum\limits_{j=0}^{\lfloor \frac{ax+b}{c} \rfloor -1} (j+1)^{k}-j^{k} \end{aligned} \)
所以有：
\( \begin{aligned} \sum\limits_{x=0}^n x^{k1}{\lfloor\frac{ax+b}{c}\rfloor}^{k2} &= \sum\limits_{j=0}^{M-1} ((j+1)^{k2}-j^{k2}) \sum\limits_{x=0}^n x^{k1} [\lfloor \frac{ax+b}{c}\rfloor > j] \\ &= \sum\limits_{j=0}^{M-1}((j+1)^{k2}-j^{k2})(S_{k1}(n)-S_{k1}(t)) \\ &= M^{k2}S_{k1}(n)-\sum\limits_{j=0}^{M-1}((j+1)^{k2}-j^{k2})S_{k1}(t) \end{aligned} \)
左半部分很好算，关注右半部分。我们知道，\(k\) 次自然数幂和是一个多项式。(\(A\) 是多项式系数。)
\( \begin{aligned} \sum\limits_{j=0}^{M-1}((j+1)^{k2}-j^{k2})S_{k1}(t) &= \sum\limits_{j=0}^{M-1}((j+1)^{k2}-j^{k2})\sum\limits_{k=0}^{k1+1}A_{k1,k} t^k \\ &= \sum\limits_{k=0}^{k1+1} A_{k1,k} \sum\limits_{j=0}^{M-1}((j+1)^{k2}-j^{k2})t^k \\ &=\sum\limits_{k=0}^{k1+1}A_{k1,k}\sum\limits_{j=0}^{M-1}\sum\limits_{a=0}^{k2-1}C_{k2}^aj^a t^k \end{aligned} \)