[专题总结]基础数论

基础同余公式

记录一些比较显然但是我一眼看不出的东西，一般把同余柿子展开成一个等式就可以证明，会动态更新。

• \(a\equiv b \pmod m,d|a,d|b,d|m \Leftrightarrow \frac a d\equiv \frac b d \pmod {\frac{m}{d}}\)


• \(a\equiv b \pmod m,d|m \Rightarrow a\equiv b \pmod d\)


• \(a\equiv b\pmod{P_1},a\equiv b\pmod{P_2} \Leftrightarrow a\equiv b\pmod {\rm{lcm}(P_1, P_2)}\) 形成双射


• \(\gcd(a,b)=\gcd(a,b\pm a)=\gcd(a\pm b,b) \Rightarrow \gcd(a,b)=1,\gcd(a,a\%b)=1\)


• \((x-1)|(x^k-1)\) 证明考虑 \(x^k-1=(x-1)\sum_{i=0}^{k-1} x^i\)


• \(\gcd(x^a-1,x^b-1)=x^{\gcd(a,b)}-1\) 证明考虑 \(x^a=x^{kb+p}, \gcd(x^a-1,x^b-1)=\gcd(x^{kb+p}-1,x^b-1)=\gcd(x^{kb}(x^p-1)+x^{kb}-1,x^b-1)=\gcd(x^ {p}-1,x^b-1)\) ，辗转相除即可证明。


• \(\gcd\) 有结合律和覆盖性， \(\gcd\) 里面可以从加好拆出来他的倍数，从乘号拆出来和他互质的数.

素数

这里咕一下 Miller-Rabin 与 Pollard-Rho

Exgcd,裴蜀定理,二元一次方程(线性同余方程)通解

感觉这个其实也挺好理解了,就是在回溯的过程维护一下两个解.

Exgcd要是理解了,裴蜀定理就可以构造既证明了?

让我们写一下裴蜀定理 \(ax+by\equiv \gcd(a,b) \mod m\) \(a,b\)是不为0的整数,则存在整数 \(x,y\) 使其有解,在 \(\gcd\) 的过程上归纳即可。

要求出他的所有解，可以给 \(x\) 加 \(\frac{b}{(a,b)}\)， \(y\) 减 \(\frac{a}{(a,b)}\) 即可。

(扩展)欧拉函数,(Ex)欧拉定理,费马小定理,乘法逆元

欧拉函数

定义： \( 有多少个数满足和 \(n\) 互质。

计算式：把 \(n\) 分解成 \(\prod p_i^{c_i}, \varphi(n)=n\times \prod \frac{p_i-1}{p_i}\).

证明，考虑容斥原理，枚举 \(x,n\) 的 \(\gcd\) 包含了几个因子.

得到 \(\varphi(n)=n\times \sum \frac{(-1)^{|S|}}{\prod_{i \in S} p_i}=n\times \prod \frac{p_i-1}{p_i}\)

性质：

1. 积性， \(a\bot b , \varphi(ab)=\varphi(a)\varphi(b)\)。


2. 对于质数 \(\varphi(p)=p-1\)。 直接根据定义即可。


3. 对于质数的次幂 \(\varphi(p^k)=p^{k-1}(p-1)\), 根据计算式展开即可。
   
   3+. 对于 \(a|b,\varphi(ab)=a\times \varphi(b)\) 同样是根据定义式展开。


4. \(\sum_{d|n} \varphi(d)=n\) 证明 : \(n=\sum_{d|n} \sum_{i=1}^n [\gcd(i,n)==d]=\sum_{d|n} \varphi(\frac{n}{d})\)


5. \(2|\varphi(n)\) , 对于 \(n>2\), 因为和他互质的数是成对出现的 \((x,n)=1,(n-x,x)=1\)


6. 欧拉函数扩展， \( 有多少个数满足和 \(n\) 的 \(\gcd=k\), \(ans=\varphi(\frac{n}{k})\) \(\gcd=k\) 。 证明：直接把 \(k\) 提出来即可，剩下的就变成了互质。


7. \(\varphi(ij)=\frac{\varphi(i)\varphi(j)(i,j)}{\varphi((i,j))}\), 证明把柿子用定义拆开即可。

(Ex) 欧拉定理，费马小定理

欧拉定理

\(a\bot p \Rightarrow a^k\equiv a^{k \mod \varphi(p)} \mod p\) 。

费马小定理

\(p \in prime \Rightarrow a^{p-1}\equiv 1 \mod p,a^{p-2}\equiv a^{-1} \mod p\) 。

证明

考虑 \(\mod p\) 意义下的简化剩余系，也就是只考虑与 \(p\) 互质的 \(\varphi(p)\) 个数，这些数乘起来永远不会是 \(p\) 的倍数,设他们分别是 \(k_1,k_2,..,k_{\varphi(p)}\) ，由于不存在 \(i,j\) 满足 \(k_i\times a \equiv k_j \times a \mod p\), 并且 \(a \times k_i\) 仍然与 \(p\) 互质， 那么每个 \(k_i \times a\) 唯一对应一个 \(k_j\), \(\prod_{i=1}^{\varphi(p)} k_{i}\equiv \prod_{i=1}^{\varphi(p)} k_{i} a \mod p \Rightarrow a^{\varphi(p)} \equiv 1 \mod p\) , 欧拉定理就可以得证。

扩展欧拉定理

\(a \not\bot p, k>\varphi(p), a^k\equiv a^{k \% \varphi(p)+\varphi(p)} \mod p\) , 不会证明。

扩展欧拉定理降幂塔

求 \(2^{2^{2^{2^{...^2}}}}\) 无穷个 \(2\) 的次方的结果 \(\mod p\) 的值。

由于是无穷，直接套用扩展欧拉定理， 直接定义 \(F_p= ans \mod p\), 有 \(F_{p}=2^{F_{p \mod \varphi(p)} + \varphi(p)}\) 当 \(p=1\) 的时候结果是 \(0\) ，对于 \(p\) , 有 \(\varphi(p)\) 是偶数，对于一个偶数， \(\varphi(p) \leq p/2\) , 所以在 \(\log\) 次可以完成。

(Ex)CRT,线性同余方程组

CRT

你有若干个同余方程 \(\left\{\begin{matrix} a \equiv m_1 \mod p_1 \\

a \equiv m_2 \mod p_2 \\

... \\

a\equiv m_k\mod p_k\end{matrix}\right.\) , 满足 \(p_1,p_2,...,p_k\) 两两互质, 你想求出 \(a \mod \prod p_i\) 的值，CRT 这个定理保证了 \(a \mod \prod p_i\) 有唯一的解（awa CRT 是个定理而不是一个算法知不知道啊？

首先一个数只会映射出来一组 \(\{m_1,m_2,...,m_p\}\) , 为什么一组 \(\{m_1,m_2,...,m_p\}\) 只会对应一个 \(a\) ? 下面的 Excrt 给出了一个构造性证明方法，可以去下面看。

CRT 同时给出了一个构造方法，求出 \(\prod_{j \not ={i}}p_j\) 在 \(\mod p_i\) 意义下的逆元 \(t_i\), 那么，我们加入一个 \(t_i \times p_i\) 会且仅会给 \(\mod p_i\) 的值加一，其他的都不变，所以， \(\sum m_i p_i t_i\) 就是答案。

ExCRT

有若干个同余方程 \(\left\{\begin{matrix} a \equiv m_1 \mod p_1 \\

a \equiv m_2 \mod p_2 \\

... \\

a\equiv m_k\mod p_k\end{matrix}\right.\) , 不一定满足 \(p_1,p_2,...,p_k\) 两两互质

假设现在有两个方程 \(\left \{ \begin{matrix} a \equiv m_1 \mod p_1 \\

a \equiv m_2 \mod p_2 \end{matrix}\right.\) 考虑怎么合并。

我们有第一个方程的解，考虑怎么合并上第二个方程，也就是要满足 \(m_1+k\times p_1 \equiv m_2 \mod p_2\) , 求出这个 \(k\) 就可以得到新的答案。

把方程写成 \(k\times p_1 +z\times p_2=m_2-m_1\) , 用 exgcd 求出来一组解，得到 \(k\) 就可以得到新答案。

code

Crt在高次解的数量的扩展

假如有一个方程在 \(\mod P\) 意义下有很多解，我们可以求出来他在每个 \(\mod p_i^{e_i}\) 的意义下解的数量，然后乘起来就是 \(\mod P\) 意义下解的数量。

证明的话，一组 \(\mod P\) 意义下的解肯定可以映射到一组 \(\mod p_i^{e_i}\) 下的解 \(\{ans_1,ans_2,...ans_k\}\) , 一组 Ans 映射回去直接参考 CRT 即可。

很多时候，直接求 \(\mod P\) 意义下的解并不方便，拆开看你有更多性质。

威尔逊定理

\(p \in prime \Leftrightarrow (p-2)!\equiv 1 \mod p\) 证明不太会。

(Ex)lucas,Kummer定理

Kummer

用来计算一个组合数内包含一个质因子的次数。

首先有一个经典的计算一个阶乘里面包含 \(p\) 的次数的方法，\(\sum_{i=0}^{\infin} \lfloor n/p^i \rfloor\) ，就是用线性性拆开之后统计包含 \(p\) 的次数 \(\geq i\) 的数的个数。

组合数 \(\binom {n + m}{n}\) 中包含 \(p\) 的次数就是 \(n,m\) 写成 \(p\) 进制的情况下， \(n+m\) 的进位次数。

那么答案可以写成 $\sum_{i=0}^{\infin} \lfloor (n+m)/p^i \rfloor-\lfloor n/p^i \rfloor- \lfloor m/p^i \rfloor $

对于每个 \(i\) ，计算去掉 \(n,m\) 的后 \(i\) 位之后 \(n+m\) 是否等于 \(n\) 的加上 \(m\) 的，要想在这里有贡献，那么必须前面进上来一个位。

所以， \(\binom n m\) 内包含 \(p\) 的次数等于把 \(n.m\) 写成 \(p\) 进制之后相加的进位次数。

Lucas

用来解决模数(是质数)很小但是 \(n,m\) 很大的组合数计算。

\(\binom n m \equiv \binom {n\% p}{m \% p}\binom{n/p}{m/p} \mod p\) 也就是这个组合数 \(\mod p\) 的值就是把它写成 \(p\) 进制之后每一位上面的组合数乘起来。

证明： 先来一个重要的柿子 \((1+x)^p\equiv 1+x^p \mod p\) .

证明直接考虑二项式展开，然后根据 Kummer 定理得到，只有 \(i=0/p\) 的时候组合数 \(\mod p=1\) 其余情况都是 \(0\)， 所以容易得到 \((1+x)^p\equiv 1+x^p \mod p\)。

然后我们就是求 \(\displaystyle \binom n m = [x^m](1+x)^{n}=[x^m]\sum_{i=0}(1+x)^{a_i p^i}=[x^m]\sum_{i=0}(1+x)^{a_i p^i}=[x^m]\sum(1+x^{p^i})^{a_i}\)。

同理，我们把 \(m\) 也拆开，因为这些洗漱并没有相交的地方，所以可以直接拆开。

\(\displaystyle \binom n m =[x^{\sum b_ip^i}]\sum(1+x^{p^i})^{a_i}=\prod[x^{b_ip^i}](1+x^{p^i})^{a_i}=\prod [x^{b_i}](1+x)^{a_i}=\prod \binom {a_i} {b_i}\)

ExLucas

用来解决模数(不一定是质数)很小但是 \(n,m\) 很大的组合数计算。

主要是发现模数不是质数没法求逆元，然后我们想办法解决这个问题。

先把模数拆成 \(\prod p_i^{c_i}\) , 对每个质数的次幂求出答案最后用 CRT 合并。

求一个 \(p^e\) 的答案，可以提出分子分母上的所有 \(p\), 这样就可以求逆元了，设 \(n!\) 中 \(p\) 的个数是 \(v(n)\)。

那么， \(\displaystyle \binom n m \equiv \frac{n!}{m! (n-m)!} \equiv \frac{n!/p^{v(n)}}{(m!/p^{v(m)})((n-m)!/p^{v(n-m)})} p^{v(n)-v(m)-v(n-m)} \mod p^e\) , 由于分母不含 \(p\) 所以与 \(p^e\) 互质，我们就可以用 exgcd 求出它的逆元了。

现在，问题变成了求 \(n!/p^{v(n)}\) 也就是求出这个阶乘去掉所有的 \(p\) 之后的数。

$n!=1\times 2 \times 3 \times ... \times n = [1 \times 2 \times ... \times p - 1] \times p \times [p+1 \times p+2 \times ... \times 2p - 1] \times 2p \times ... $ 我们这一次把所有的 \(p\) 的倍数 \(p,2p,3p,4p,...kp\) 提出来，把它们每个人都除掉一个 \(p\), 然后剩下的 \(1,2,3,..k\) 就是一个等价的问题，可以递归下去，最后所有的 \(p\) 都会被除掉。

接下来的问题就是若干个 \(\prod_{i=1}^{p-1}(kp+i) \mod p^e\) , 由于 \(k\) 可能 \(\geq p\) , 所以我们对 \(p^c\) 内的数计算一个 \(pre(n)=\prod_{i=1}^n [i \% p \not= 0] i\) ， 计算的时候直接用 \(pre(p^e-1)\) 的若干次方配上一个散块的即可。

code

(Ex)bsgs

用来求解 \(a^x\equiv c \mod p\) 的 \(x\) 的问题，其中 \(a \bot p\) 。

采用分块的思想， \(a^{kB+t} \equiv c \mod p \Rightarrow a^{kB} \equiv ca^{-t} \mod p\) ，由于互质直接求出逆元，对于 \([0,B)\) 每个数把 \(ca^{-t}\) 放到 hash 表里面，然后拿 \(a^{kB}\) 一个一个去查，查到了就是解。

当 \(a\not\bot p\) 的时候，我们无法求解逆元，不能直接使用 bsgs ，exbsgs 应运而生。

最简单的想法就是把它们变得互质， \((a,p)=d\), 如果 \(d\not|c\) ， 那么肯定无解（因为 \((c,p)\) 永远不可能等于 \((a^u,p)\)。

如果整除，那么可以给所有的数都除掉 \(d \Rightarrow a^{x-1} \frac{a}{d} \equiv \frac{c}{d} \mod \frac{p}{d} \Rightarrow a^{x-1} \equiv \frac{c}{d} (\frac{a}{d})^{-1} \mod \frac{p}{d}\) 由于 \((\frac{p}{d},a)\) 不一定等于 \(1\), 而除掉 \(d\) 之后的问题和原来一样，所以直接一直递归下去直到互质，互质之后套用一个 bsgs 即可。

每递归一次要给答案加一，注意判断中间 \(x\) 就等于 \(1\) 的情况。

code

原根,阶,高次剩余

阶

最小的 \(x\) 使得 \(a^x \equiv 1 \mod p\) ， 记为 \(\delta_p(a)\)

对于 \(a \not\bot p\) 的情况，不存在阶，对于 \(a\bot p\), 阶的上界是 \(\varphi(p)\) .

性质1: \(a^x \equiv 1 \mod p\) 当且仅当 \(\delta_p(a)|x\) .

证明，如果存在 \(a^r \equiv 1 \mod p, \delta_p(a) \not|r\) ，由于存在 \(r-k\delta_p(a)<\delta_p(a)\) ，且 \(a^{k\delta_p(a)}\equiv a^r\equiv 1\mod p \Rightarrow a^{r-k\delta_p(a)} \equiv 1 \mod p\) ，这与阶是最小的数矛盾，所以不存在这样的 \(r\)。

性质2: \(\displaystyle \delta_p(a^k)=\frac{\delta_p(a)}{(\delta_p(a),k)}\)

首先所有的 \(a^x \equiv 1 \mod p \Rightarrow a^{kx} \equiv 1 \mod p\) ，所以 \(\delta_p(a^k)\) 是 \(\delta_p(a)\) 的约数。

根据性质 \(1\), 我们就是要找到一个最小的 \(x\) 使得 \(\delta_p(a)|kx\) 可知 \(x_{min}=\frac{\delta_p(a)}{(\delta_p(a),k)}\)

原根

阶是 \(\varphi(p)\) 的数称为 \(p\) 的原根，有且仅有 \(2,4,p^e,2p^e\) 存在原根， 其中 \(p\in Prime\)。

• 原根的性质：假设 \(p\) 存在一个原根 \(g\), \(g\) 可以把 \(\mod p\) 意义简化剩余系（只保留与 \(p\) 互质的数）全部表示成 \(g^k\) 。

证明 : 与 \(p\) 互质的数有 \(\varphi(p)\) 个，又因为 \(g\) 的阶是 \(\varphi(p)\) , 可以表示 \(\varphi(p)\) 个数，并且每个数都是和 \(p\) 互质的，所以只需要保证任意两个 \(i,j<\varphi(p)\) ，不存在 \(g^{i} \equiv g^{j} \mod p\) 即可。

假设存在 \(i,j\) , \(g^{i-j} \equiv 1 \mod p\), 由于 \(i-j<\varphi(p)\) ，这与 \(g\) 是阶矛盾。

• 原根的判定：只需要判定所有的 \(k<\varphi(p)\) 都不存在 \(g^k \equiv 1 \mod p\) 即可。

首先我们只用判断 \(\varphi(p)\) 的约数，因为如果存在不是 \(\varphi(p)\) 的因子也满足的话，可以取出来最小的之后反证，也可以导出矛盾。

判断所有的因子，可以找出 \(p\) 的所有真因子 \(q_i\), 判断所有是否有 \(a^{\frac{\varphi(p)}{q_i}} \not\equiv 1 \mod p\)， 因为如果存在一个约数 \(k, a^k\equiv 1\mod p\) ，那么肯定存在一个 \(\frac{\varphi(p)}{q_i}\) 是他的倍数，满足 \(a^{\frac{\varphi(p)}{q_i}} \equiv 1 \mod p\) ， 同理所有的 \(\frac{\varphi(p)}{q_i}\) 也可以覆盖他的所有因子，加入所有的 \(\frac{\varphi(p)}{q_i}\) 都不同余 \(1\), 那么就可以说明他是一个原根。

• 原根的个数 ：满足 \(\delta_p(a)=l\) 的数的个数为 \(\left \{ \begin{matrix} 0 && l \not| \varphi(p) \\
  
  \varphi(l) && l|\varphi(p) \end{matrix} \right.\)

把 \(a\) 表示成 \(g^k\), 就是求有多少个 \(k\) 满足 \(\delta_p(g^k)=l\) ,由于 \(\delta_p(g^k)=\frac{\delta_p(g)}{(\delta_p(g),k)}=\frac{\varphi(m)}{(\varphi(m),k)}=l\) ， 也就是求有多少个 \(k\) 满足 \((\varphi(m),k)=\frac{\varphi(m)}{l}\) ，根据欧拉函数的性质可以知道这样的 \(k\) 有 \(\varphi(\frac{\varphi(m)}{\frac{\varphi(m)}{l}})=\varphi(l)\) 个。

所以原根的个数有 \(\varphi(\varphi(m))\) 个。

高次剩余

求一个满足 \(x^k\equiv c \mod p\) 的 \(x\) ，利用原根把它搞到指数上。

令 \(x=g^{rt_x}, c=g^{rt_c}\) ,也就是求一个 \(rt_x\) 满足 \(g^{rt_x k} \equiv g^{rt_c} \mod p \Rightarrow rt_x k \equiv rt_c \mod (p-1)\) ， 这个是一个经典的 exgcd 问题，解出来一个 \(k\) 回带回去即可，这个过程需要求 \(p\) 的原根和 \(c\) 的 \(rt_c\)

code

拉格朗日插值

对于一个 \(k\) 次的多项式，我们知道他的 \(k-1\) 个 \((x_i,y_i)\) , 就可以确定他的表达式，进而求出任意一个 \(x\) 的 \(y\) 。

表达式具体是什么呢？ 拉格朗日大神给出了一个构造 \(f(x)=\displaystyle \sum_{i=1}^n y_i \prod_{j\not ={i}} \frac{x-x_j}{x_i-x_j}\) 。

发现这个柿子把每个 \(x_i\) 带进去得到的都是 \(y_i\)， 那么它一定正确的表示了这个多项式。

code

直接暴力求解一个，复杂度 \(O(n^2)\) , 如果满足横坐标是连续的，那么我们可以把分子分母用前后缀积拼凑起来，具体的，对于一个 \(x\), 处理 \(x-j\) 的前缀积，阶乘的前缀积的逆即可。

code

题目

P3543 [POI2012]WYR-Leveling Ground

先差分，我们的目的是把每个数表示成 \(ax_i+by_i\) 的形式，是的 \(\sum x_i=0,\sum y_i=0\) ， 且最小化 \(\sum x_i+y_i\)。

限制很多，我们一个一个来看，先看如何表示成 \(ax_i+by_i\) ，显然只需要 exgcd 一下。

然后考虑 \(\sum x_i=0,\sum y_i=0\)， 不妨考虑在序列最后一项加入一个 \(n+1\)。

这样 \(a*\sum x+b*\sum y = \sum_{i=1}^{n+1} C_i-C_{i-1} = 0\)。

我们保证 \(\sum x = 0\)， 那么 \(\sum y\) 就是 \(0\) ，假设现在 \(\sum x > 0\), (<0 同理)，为了调整出来，我们只需要拿出来任意一个 \(x_i\) 让他加 \(\frac{b}{(a,b)}\) , 然后让 \(y_i\) 减 \(\frac{a}{(a,b)}\)，这样不改变 exgcd 的结果，并且还可以调成 \(\sum x, \sum y\)，这样一定可以调整出来，因为它取遍了全部的情况。

再来考虑最小化，发现一个人的贡献就是 \(\frac{|x|+|y|}{2}\) ，初始我们找到每个 exgcd 最小的 \(x+y\) ，调整的时候用堆找到 \(|x+\frac{b}{(a,b)}|+|y-\frac{a}{(a,b)}|-(|x|+|y|)\) 的最小值，每次找最小的代价去调整即可。

ABC245 Ex - Product Modulo 2

NOI 模拟8.16 C. 数数

$The \ light \ has \ betrayed \ me$