扩展欧几里得
用途:
求解逆元、好像还可以解二元一次不定方程。
说句闲话：数学课老师让解二元一次方程组，讲题直接扩欧：“这显然是跑两遍EXGCD，求出最小解加膜数取个交集即可。”
于是我写了满满一黑板递归。。。
初初初阶
推导
我们已知 $a,b$ 要求 $x,y$， 使 $ax + by = \gcd(a,b)$
那么，我们可以得到：$bx'+(a \mod b)y' = \gcd(b,a \mod b)$
所以：$bx' + (a-b\lfloor\dfrac{a}{b}\rfloor)y' = \gcd(b,a \mod b)$
$ay' + b(x' + \lfloor\dfrac{a}{b}\rfloor y') = \gcd(b,a \mod b)=ax + by$
为了使等式成立我们得到：$x=x'$，$y = (x' + \lfloor\dfrac{a}{b}\rfloor y')$ 以此递归下去，最后当 $b = 0$ 时，$x = 1,y = 0$ 再归回去就行。
所以代码实现是这样的：
inline int exgcd(int a,int b){
if(b == 0){x = 1;y = 0;return a;}
int g = exgcd(b,a%b);
int t = x;
x = y;
y = t - a/b*y;
return g;
}
初初阶
通常我们用拓展欧几里得求解最小正整数解问题。
设 $g = gcd(a,b)$，求，满足 $ax+by=g$ 的最小的正整数 $x$;
当我们用扩展欧几里得求出满足 $ax+by=g$ 的 $x,y$ 时，我们对其再做一下变形：
即：$a(x+k\dfrac{b}{g})+b(y-k\dfrac{a}{g})= g$
所以对于 $x$，加 $k$ 个 $\dfrac{b}{g}$ 都不影响等式成立。所以我们不妨把它看做一个周期 $T = \dfrac{b}{g}$。
那么我们可以得到，倘若扩展欧几里得跑完之后，$x$ 是一个负数，我们可以对其加一些 $T$ 让它变成正数，再找最小值即可。
对于求最小值，我们有 $x_{min}=((x \mod T)+T) \mod T$。
解释一下：第一个取膜，让 $|x|$ 小于 $T$。加上 $T$ 使其变成正的（前提是 $x$ 一开始是负的，是正的的话无所谓）。最后膜 $T$ 保证其最小，万无一失。（毕竟有可能加上 $T$ 以后 $x$ 比 $T$ 大，这样显然不是最小解）
code：
int g = exgcd(a,b);
int T = b/g;
x = (x%T+T)%T;
初阶
我们终于可以尝试用扩展欧几里得解二元一次不定方程了！！
给定一个方程：$ax+by=c$，我们要求 $x$ 的最小正整数解。
首先EXGCD，得到了 $ax+by=\gcd(a,b)$ 的解，令 $g = \gcd(a,b)$。
等式两边同除：$a\dfrac{x}{g}+b\dfrac{y}{g}=1$
两边同乘：$a\dfrac{cx}{g}+b\dfrac{cy}{g}=c$
这时候我们发现，当 $g \nmid c$ 时是无解的。
这样我们就解决了这类问题。
（注：当系数有负数出没，注意取反）
入门
现在可以求逆元了。
逆元定义：
使 $ax \equiv 1 (\mod p)$ 成了的 $x$，写作 $a^{-1}$。
求法：
如果 $p\perp a$ ，那么直接求 $\dfrac{1}{a}(\mod p)$ ，费马小定理就行了。
我们还可以EXGCD，就需要求出 $ax+by=1$ 的解即可。
code
#include<bits/stdc++.h>
using namespace std;
int n,p,x,y;
inline int exgcd(int a,int b){
if(b == 0){x = 1;y = 0;return a;}
int g = exgcd(b,a%b);
int t = x;
x = y;
y = t - a/b*y;
return g;
}
inline int ask(int a,int b){
x = y = 0;
int g = exgcd(a,b);
int T = b/g;
x = (x%T+T)%T;
return x;
}
int main(){
cin.tie(0);
cout.tie(0);
cin >> n >> p;
for(int i = 1;i <= n;i ++){
cout<<ask(i,p)<<endl;
}
return 0;
}
这个写法在 P3811 【模板】乘法逆元里面只能拿64分，具体满分的费马小定理做法下节再谈。
update：
2022/8/20：解决了 $\LaTeX$ 渲染问题。