即：$ax+by=1$，给定$a,b$，求$x,y$。

和欧几里得算法一样，辗转相除，每次更新外层$x,y$对即可。

需要注意的是，$ax+by=c$有解当且仅当$\gcd(a,b) |c$，需要进行特判。

由欧拉定理，若$(a,n)=1$，则$a^{\phi(m)}\equiv 1(\text{mod } m)$。

类似单位复根，数$m$的原根$g\in[1,m],(g,m)=1$满足$\{g,g^2,\ldots,g^{\phi(m)}\}$构成模$m$的一个既约剩余系。易得，对于质数$m$，这个既约剩余系的取值范围为$[1,m-1]$。

原根的另一个定义是，$\forall p<\phi(m), g^{\phi(m)}\neq 1$，即$\phi(m)$是最小的让$g^d\equiv 1(\text{mod } m)$的正整数$d$。

这两个定义可以互推，桥梁是$\forall i,j\in[1,\phi(m)],i\neq j,g^{i}\neq g^j(\text{mod }m)$。

数$n$有原根的充要条件为，$n$是$2,4,p^{a},2p^{a}$（$p$为奇素数，$a$为正整数）。这可以推出：质数必有原根。

可以通过枚举正整数$g$并验证是否满足原根的第二个定义。

设$d_i$为$\phi(m)$的所有约数，当$\forall i,g^{d_i}\neq 1$时，$g$为$m$的一个原根。

可以优化这个过程：设$p_i$为$\phi(m)$的所有质因数，则当$\forall i,g^{\frac{\phi(m)}{p_i}}\neq 1$时，$g$为$m$的一个原根。

证明很简单：若$a^{x}\equiv 1(\text{mod }m)$，则$a^{kx}\equiv 1(\text{mod }m)$。$\frac {\phi(m)}{p_i}$是除了含有$p_i^{k_i}$因子之外，所有$d_i$的倍数，故如果$\exists k\in N,k\cdot d_j=\frac{\phi(m)}{p_i},g^{d_j\cdot k}\equiv g^{\frac{\phi(m)}{p_i}}\equiv 1 $的因子通过其他部分验证。验证一圈下来除了$\prod_{i}p_i^{k_i}$即$(m)$之外（本身就要求是1）别的都得到了验证。

这样优化下来，复杂度几乎是一个常数（质因数个数增长极慢）。

假设已经求出$m$的一个原根$g$，显然对于集合$S_0=\{g^s|1\leq s\leq \phi(m)\}$中的每一个元素$x$都有$x^{\phi(m)}\equiv 1$，根据第二个定义，$\forall j\in[1,\phi(m)],(g^s)^{j}\text{ mod }m\ne 1=(g^s)^{0}$，即只有$\forall j\in[1,\phi(m)),j\cdot s\text{ mod }\phi(m) \ne 0)$，这要求$(s,\phi(m))=1$。

故集合$S=\{g^s\text{ mod }m|1\leq s\leq \phi(m),(\phi(m),s)=1\}$中包含所有关于$m$不同余（由原根$g$的性质得）的原根，个数为$\phi(\phi(m))$。

即：$a^{x}\equiv b(\text{ mod }c)$，给定$a,b,c$，求出$x$。

设$x=iB+t$（或者$x=iB-t$，都可），其中$B$为块大小，先设为$\lceil\sqrt c\rceil$。

那么有$a^{iB}\equiv b\cdot a^{-t}$，把右半部分预处理并扔进map里，从小到大枚举$i\in[0,B]$，通过扩欧解出来右半边$a^{-t}$应当取的值，查map判断，即可$O(\sqrt c)$求解。

即：$x^n\equiv a(\text{ mod }m)$，给定$m\in prime,n,a$，求出$x$。

前置芝士：扩欧，原根，$BSGS$

模板题：HDU3930 Broot（数据范围有误，应为$1e12$。数据较弱，提供几组稍强数据）

设$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} (\text{ mod }m)$式中只有$y$未知。

式子等价于：$yn\equiv z(\text{ mod }\phi(m))$，可以用扩欧求出$y$的一个解$y_0$。

设$gcd=\gcd(n,\phi(m))$，$y$的解集为$\{k\in[0, gcd)|y_0+k\cdot \frac{\phi(m)}{gcd}\}$。再根据此求出$x$即可。

类似的，设$m$的一个原根为$g$，由于$a,x\in[0,m-1]$，必有$x=0$或正整数$y$满足$g^{y}=x$。

现在$(g^{n})^{y}\equiv a (\text{ mod }m)$式中只有$y$未知。

通过$BSGS$可以求出所有符合要求的$y$，但这里的$BSGS$需要使用map<int,vector>，因为$g^n$不是原根，$a^{t}$部分并非一对一关系。过后根据$y$算出$x$即可。

这两种解法都通过了原根进行转换，第一种方法由于没有使用较为复杂的map，常数比较小；第二种方法则更加简便、易写。