====== 扩展欧几里得 ======
即： $ax+by=1$ ，给定 $a,b$ ，求 $x,y$ 。
和欧几里得算法一样，辗转相除，每次更新外层 $x,y$ 对即可。
**需要注意的是， $ax+by=c$ 有解当且仅当 $\gcd(a,b) |c$ ，需要进行特判。**
====== 原根 ======
由欧拉定理，若 $(a,n)=1$ ，则 $a^{\varphi(m)}\equiv 1\pmod m$ 。
类似单位复根，数 $m$ 的原根 $g\in[1,m],(g,m)=1$ 满足 $\{g,g^2,\ldots,g^{\varphi(m)}\}$ 构成模 $m$ 的一个既约剩余系。易得，对于质数 $m$ ，这个既约剩余系的取值范围为 $[1,m-1]$ 。
原根的另一个定义是， $\forall p<\varphi(m), g^{\varphi(m)}\neq 1$ ，即 $\varphi(m)$ 是最小的让 $g^d\equiv 1\pmod m$ 的正整数 $d$ 。
这两个定义可以互推，桥梁是 $\forall i,j\in[1,\varphi(m)],i\neq j,g^{i}\neq g^j\pmod m$ 。
===== 判断是否有原根 =====
数 $n$ 有原根的充要条件为， $n$ 可表示为 $2,4,p^{a},2p^{a}$ 的形式（ $p$ 为奇素数， $a$ 为正整数）。这可以推出：质数必有原根。
===== 求一个原根 =====
可以通过枚举正整数 $g$ 并验证是否满足原根的第二个定义。
设 $d_i$ 为 $\varphi(m)$ 的所有约数，当 $\forall i,g^{d_i}\neq 1$ 时， $g$ 为 $m$ 的一个原根。
可以优化这个过程：设 $p_i$ 为 $\varphi(m)$ 的所有质因数，则当 $\forall i,g^{\frac{\varphi(m)}{p_i}}\neq 1$ 时， $g$ 为 $m$ 的一个原根。
证明很简单：若 $a^{x}\equiv 1\pmod m$ ，则 $a^{kx}\equiv 1\pmod m$ 。 $\frac {\varphi(m)}{p_i}$ 是除了含有 $p_i^{k_i}$ 因子之外，所有 $d_i$ 的倍数，故如果 $\exists k\in \mathbb N,k\cdot d_j=\frac{\varphi(m)}{p_i},g^{d_j\cdot k}\equiv g^{\frac{\varphi(m)}{p_i}}\equiv 1 $ 的因子通过其他部分验证。验证一圈下来除了 $\prod_{i}p_i^{k_i}$即$\varphi(m)$ 之外（本身就要求是 $1$ ）别的都得到了验证。
这样优化下来，复杂度几乎是一个常数（质因数个数增长极慢）。
===== 求所有原根 =====
假设已经求出 $m$ 的一个原根 $g$ ，显然对于集合 $S_0=\{g^s|1\leq s\leq \varphi(m)\}$ 中的每一个元素 $x$ 都有 $x^{\varphi(m)}\equiv 1$ ，根据第二个定义， $\forall j\in[1,\varphi(m)],(g^s)^{j}\bmod m\ne 1=(g^s)^{0}$ ，即只有 $\forall j\in[1,\varphi(m)),j\cdot s\bmod \varphi(m) \ne 0)$ ，这要求 $(s,\varphi(m))=1$ 。
故集合 $S=\{g^s\bmod m|1\leq s\leq \varphi(m),(\varphi(m),s)=1\}$ 中包含所有关于 $m$ 不同余（由原根 $g$ 的性质得）的原根，个数为 $\varphi(\varphi(m))$ 。
====== BSGS ======
即： $a^{x}\equiv b\pmod c$ ，给定 $a,b,c$ ，求出 $x$ 。
设 $x=iB+t$ （或者 $x=iB-t$ ，都可），其中 $B$ 为块大小，先设为 $\left\lceil\sqrt c\right\rceil$ 。
那么有 $a^{iB}\equiv b\cdot a^{-t}$ ，把右半部分预处理并扔进 map 里，从小到大枚举 $i\in[0,B]$ ，通过扩欧解出来右半边 $a^{-t}$ 应当取的值，查map判断，即可 $O(\sqrt c)$ 求解。
====== N次剩余 ======
即： $x^n\equiv a\pmod m$ ，给定 $m\in prime,n,a$ ，求出 $x$ 。
前置芝士：扩欧，原根， BSGS
模板题：[[http://acm.hdu.edu.cn/showproblem.php?pid=3930|HDU3930 Broot]]（数据范围有误，应为 $1e12$ 。数据较弱，提供[[https://paste.ubuntu.com/p/gC2QR6tFcq/|几组稍强数据]]）
==== 解法1 ====
设 $m$ 的一个原根为 $g$ ，由于 $a,x\in[0,m-1]$ ，必有 $x=0$ 或正整数 $y$ 满足 $g^{y}=x$ ， $a=0$ 或正整数 $z$ 满足 $g^{z}=a$ 。
容易通过 BSGS 求出 $z$ ，现在 $g^{yn}\equiv g^{z} \pmod m$ 式中只有 $y$ 未知。
式子等价于： $yn\equiv z\pmod \varphi(m)$ ，可以用扩欧求出 $y$ 的一个解 $y_0$ 。
设 $gcd=\gcd(n,\varphi(m))$ ， $y$ 的解集为 $\{k\in[0, gcd)|y_0+k\cdot \frac{\varphi(m)}{gcd}\}$ 。再根据此求出 $x$ 即可。
#include
#include
#include
#include
\\
==== 解法2 ====
类似的，设 $m$ 的一个原根为 $g$ ，由于 $a,x\in[0,m-1]$ ，必有 $x=0$ 或正整数 $y$ 满足 $g^{y}=x$ 。
现在 $(g^{n})^{y}\equiv a \pmod m$ 式中只有 $y$ 未知。
通过 BSGS 可以求出所有符合要求的 $y$ ，但这里的 BSGS 需要使用 ''%%map%%'' ，因为 $g^n$ 不是原根， $a^{t}$ 部分并非一对一关系。过后根据 $y$ 算出 $x$ 即可。
这两种解法都通过了原根进行转换，第一种方法由于没有使用较为复杂的 ''%%map%%'' ，常数比较小；第二种方法则更加简便、易写。
#include
#include
#include
#include