数学-JZTXT

欧拉定理

定理内容：$a^{\varphi(m)} \equiv 1 (\bmod m), a\perp m \Rightarrow a^{b} \equiv a^{b \ \bmod \ \varphi(m)}(\bmod m) , a\perp m$。
证明：设 $\{r_1,r_2,\cdots,r_{\varphi(m)}\}$ 为 $\bmod m$ 下的一个简化剩余系，那么 $\{ar_1,ar_2,\cdots,ar_{\varphi(m)}\}$ 也是 $\bmod m$ 下的一个简化剩余系（否则存在 $ar_x\equiv ar_y(\bmod m)$ 或 $\gcd(ar_x,m) \not=1$，两者都显然不成立），所以 $r_1r_2r_3\cdots r_{\varphi(m)} \equiv a^{\varphi(m)}r_1r_2r_3\cdots r_{\varphi(m)} (\bmod m)$，即证。
扩展欧拉定理：$a^{b} \equiv a^{\min(b,b \ \bmod \ \varphi(m)+\varphi(m))} (\bmod m)$，**不要求 **$a \perp m$。

直观理解是循环节长度为 $\varphi(m)$ ，但是降幂降到 $b \bmod \varphi(m)$ 的时候可能跳到了循环前的混循环，所以再加上 $\varphi(m)$ 跳进循环节。

以下假设 $b \geq \varphi(m)$ ，证明考虑分解 $m$ ，对于每个 $p_i^{q_i}$ 证明 $a^{b} \equiv a^{\min(b,b \ \bmod \ \varphi(m)+\varphi(m))} (\bmod p_i^{q_i})$ 即可。
- 若 $\gcd(a,p_i^{q_i})=1$，那么 $\varphi(p_i^{q_i}) \mid \varphi(m)$，故 $a^b \equiv a^{\lfloor\frac{b}{\varphi(m)} \rfloor \varphi(m) + b \ \bmod \ \varphi(m)} \equiv a^{b\ \bmod \ \varphi(m)}$ 。
- 否则，有 $p_i \mid a$，则 $q_i \leq \varphi(m) \leq b$（$q_i \leq \varphi(p_i^{q_i})$ 可以把右边拆开直接证），故 $p_i^{q_i} \mid a^{b\ \bmod\ \varphi(m) +\varphi(m)}$ ，即 $a^b \equiv 0 \equiv a^{b\ \bmod\ \varphi(m) +\varphi(m)} (\bmod p_i^{q_i})$。
例题：P4139 上帝与集合的正确用法

直接 $2^{2^{2^{\cdots}}} \equiv 2^{2^{2^{\cdots}} \bmod \ \varphi(p) +\varphi(p)} (\bmod p)$ ，递归到 $p=1$ 时让式子返回 $0$ 即可。

扩展欧几里得算法

内容：求解 $ax+by=d$。

假设已经求得了 $ax+ (b \bmod a) y =d$ 的解 $x,y$ ，那么有 $ax+ (b- \lfloor \dfrac{b}{a} \rfloor) y =d \Rightarrow a(x-\lfloor \dfrac{b}{a} \rfloor y)+by =d$
例题：解 $a^x \equiv x (\bmod m) , m \leq 10^9$。
- 法一：直接令 $x=a^{a^{a \cdots}} (\bmod m)$ 即可。
- 法二：$a^x \equiv x (\bmod m)$
  
  若 $a \perp m$，令 $x = y +k\varphi(m)$，那么有 $a^y \equiv y+k \varphi(m) (\bmod m)$，所以 $a^y = y+k \varphi(m)+lm$ ，故 $a^y = y + t\gcd(\varphi(m),m)$，于是 $a^y \equiv y (\bmod \gcd(m, \varphi(m)))$。这样就成功降成了一个子问题，只需要用 exgcd 解出 $k$
  
  即可，同时每次 $O(\sqrt m)$ 暴力算 $\varphi(m)$，复杂度为 $O(\sqrt m +\sqrt{m/2}+ \cdots) =O(\sqrt m)$ 。
  
  若 $a \not \perp m$，没看懂。

中国剩余定理

内容：若 $m_1,m_2,\cdots m_n$ 两两互质，那么方程组 $x \equiv a_i (\bmod m_i)$ 的解为：

令 $M=\prod m_i,n_i=M\cdot m_i^{-1},c_i=n_i\cdot (n_i^{-1} \bmod m_i)$，则 $x \equiv \sum\limits_{i=1}^na_ic_i (\bmod M)$。
性质：一组 $(a_1,a_2,\cdots,a_n)$ 和一个解 $x$ 构成双射。
exCRT：设 $x\equiv a_1 (\bmod m_1),x \equiv a_2(\bmod m_2)$，那么 $x=m_1p+a_1=m_2q+a_2$，于是 $m_1p-m_2q=a_2-a_1$，用 exgcd 直接解即可，时间复杂度 $O(n \log V)$。

单位根反演

内容： $\dfrac{1}{d}\sum\limits_{k=0}^{d-1} \omega_d^{kn}=[d \mid n]$。
例题：$\displaystyle{\sum\limits_{i \geq 0} \binom{n}{id}=\sum\limits_{k \geq 0} \binom{n}{k}[d \mid k]}=\frac{1}{d}\sum\limits_{i=0}^d\sum\limits_{k=0}^n (\omega_d^i)^k \binom{n}{k}=\frac1d\sum\limits_{i=0}^d(1+\omega_d^i)^n$

对 $998244353$ 取模，满足 $d=2^k$，令 $\omega_d=3^\frac{\varphi(998244353)}{d}$ 即可。

BSGS算法

内容：$a^x \equiv b (\bmod p) , a \perp p$。取 $d=\lceil \sqrt p \rceil$，那么 $a^{dx-y} \equiv b (\bmod p)$，于是 $a^{dx} \equiv ba^y (\bmod p) $，枚举一边，另一边用哈希表查即可。多组询问取 $d=\sqrt \frac{p}{T}$ 即可做到 $O(\sqrt Tp)$。这个折半思想有更多应用。
扩展BSGS：设 $d_1=\gcd(a,p)$，则要求 $d_1 \mid b$，两边除 $d_1$ 得到 $\dfrac{a}{d_1} \cdot a^{x-1} \equiv \dfrac{b}{d_1} (\bmod \dfrac{p}{d_1})$，如果 $\gcd(a,\dfrac{p}{d_1}) \not=1$ 就继续除，最后得到 $\dfrac{a^k}{D} \cdot a^{x-k} \equiv \dfrac{b}{D} (\bmod \dfrac{p}{D})$，然后用 BSGS 即可，复杂度 $O(\log p+\sqrt p)$。

二次剩余

内容：求解 $x^2 \equiv a (\bmod p)$，$p$ 为奇质数。

首先有 $x^{2 \cdot \frac{p-1}{2}} \equiv a^{\frac{p-1}2} \equiv 1 (\bmod p)$，所以要求 $a^{\frac{p-1}2} \equiv 1 (\bmod p)$。
性质：
- $x^2 \equiv a (\bmod p)$ 只有两个解：对于 $x_1,x_2$ 两个解，有 $(x_1-x_2)(x_1+x_2)\equiv 0 (\bmod p)$，于是 $x_1+x_2 \equiv 0 (\bmod p)$，所以一个方程恰好有两个互为相反数的解。
- 也可以知道一对相反数和一个二次剩余构成双射，那么 $\bmod p$ 的二次剩余数量恰为 $\dfrac{p-1}2$。
Cipolla算法：若 $a$ 满足 $\omega=t^2-a$ 不是 $p$ 的二次剩余，那么 $x=(t+\sqrt \omega)^{\frac{p+1}2}$ 是 $x^2 \equiv a (\bmod p)$ 的解。证明则由于 $x^p \equiv x (\bmod p) \Rightarrow t^p \equiv t (\bmod p)$，而 $(\omega^{\frac{p-1}2})^2 \equiv 1 (\bmod p)$，而 $\omega^{\frac{p-1}2} \not \equiv 1 (\bmod p)$（否则 $\omega ^{\frac{p-1}2} \equiv 1 \equiv x^{p-1} (\bmod p) \Rightarrow \omega \equiv x^2 (\bmod p)$），所以 $\sqrt \omega ^{p-1} \equiv \omega ^{\frac{p-1}2} \equiv -1 (\bmod p)$ ，那么 $x^2=(t+\sqrt \omega)^{p+1} \equiv (t+\sqrt \omega)^p(t+\sqrt \omega) \equiv (t^p+\sqrt w ^p)(t+\sqrt \omega) \equiv(t-\sqrt \omega) (t+\sqrt \omega) \equiv t^2-\omega \equiv a(\bmod p) $

由于 $\bmod p$ 的二次剩余有 $\dfrac{p-1}{2}$ 个，所以随机选 $a$ 的复杂度是 $O(1)$ 的。
勒让德符号：

$(\dfrac{a}p) = \begin {cases} 1, \exist b \ s.t. b^2 \equiv a (\bmod p)\\ 0, p \mid a\\ -1,otherwise \end {cases} = a^{\frac{p-1}2} (\bmod p)$。
相关结论：
- $(\dfrac ap)(\dfrac bp)=(\dfrac {ab}p)$。
- $(\dfrac {a^2} p) = \begin {cases} 0,p \mid a \\ 1 ,otherwise\end {cases}$
- 二次互反律：对于奇质数 $p,q$，$(\dfrac pq)(\dfrac qp) = (-1)^{\frac{p-1}2\frac{q-1}2}$。
- $(\dfrac 2p)=(-1)^{\frac{p^2-1}{8}}$。
- $\sum\limits_{i=1}^{p-1} (\dfrac ip)=0 \Leftarrow $ 恰好有 $\dfrac{p-1}{2}$ 个二次剩余。
例题：计算 $x^2+y^2 \equiv r (\bmod p)$ 的解的数量。

$x^2 \equiv a (\bmod p)$ 的解的数量为 $1+ (\dfrac ap)$。

所以答案为 $\sum\limits_{i=0}^{p-1} ((\dfrac ip)+1)((\dfrac{r-i}p)+1)=p + 2\sum\limits_{i=0}^{p-1} (\dfrac{i}{p}) + \sum\limits_{i=0}^{p-1} ( \dfrac {i(r-i)}p)=p+\sum\limits_{i=1}^{p-1}(\dfrac{\frac ri-1}p)$。

若 $r=0$，那么答案为 $p+(p-1)(\dfrac {-1}p)$，否则 $\dfrac ri$ 取遍 $[1,p-1]$ ，那么答案为 $p-(\dfrac{-1}{p})$。

Lucas 定理

内容：$\displaystyle {\binom nm=\binom{\lfloor n/p\rfloor}{\lfloor m/p\rfloor} \binom{n \bmod p}{m \bmod p}}$。
证明：$\displaystyle \binom nm =[x^m](1+x)^n= [x^m] (1+x)^{p \lfloor n/p\rfloor} (1+x) ^{n \ \bmod \ p}=\binom{\lfloor n/p\rfloor}{\lfloor m/p\rfloor} \binom{n \bmod p}{m \bmod p}$。
性质：$\displaystyle \binom nm \equiv [m \in n] (\bmod 2)$。