逆元

基础运算符号

首先先介绍一下以下文章会用到的基础运算符号.

$a\equiv b$ $(mod$ $c)$ $:$ 读作 $a$ 及 $b$ 对模 $c$ 同余.及 $a-b \mod c = 0$

乘法逆元的定义

$a$ 的逆元，及一个数可以取消一个式乘上 $a$。比如说 $a$ 的乘法逆元即 $\frac{1}{a}$ ，也就是 $a$ 的倒数.
那么思考：在模 $p$意义下$a$最小的逆元还是 $\frac{1}{a}$ 吗 $？$

这里插入一个乘法逆元的模板同余方程

求一个$ax\equiv 1$ $(mod$ $b)$，这里给出$a,b$，求出 $x$ 的最小整数解.

以下将 $x$ 的乘法逆元记作 $x^{-1}$.

特殊地，$0$ 没有乘法逆元

$exgcd$ 求乘法逆元

设有一个$y \in Z$ ，满足$ax+by=1$. 因为题目中数据范围满足 $2 \leqslant a,b$且 $x \in N^+$ ，所以说必有 $y<0$.

然而 $exgcd$ 是用来求 $ax+by=gcd(a,b)$ 中的 $x,y$ 的，不能直接求出 $ax+by=1$的解。那么考虑将这个方程转化.

为了构造出 $gcd(a,b)=1$ ，考虑证明 $a,b$互质.

证明：

根据最大公因数的定义，可知$a,b\mod \gcd(a,b)=0$

\[\because \begin{cases}x \in N^+,y\in N^+,a,b\mod\gcd(a,b)=0 \\ a,b \mod \gcd(a,b)=0 \\ ax+by=1\end{cases}\]

\[\therefore ax+by \mod \gcd(a,b)=0\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \]

\[\therefore 1 \mod \gcd(a,b)=0 \]

\[\therefore \gcd(a,b)=1 \]

$exgcd$

已知$a,b$. $ax+by=gcd(a,b)$ ，方便起见，记 $G=gcd(a,b)$.

求解 $x_0$，即 $x$ 的最小整数解.

若已经求出 $x$ 的另解 $x_1,y_1$ 满足 $G=bx_1+(a \mod b)y_1$，则必有 $ax+by=bx_1+(a \mod b)y_1$①

既有未知数 $x,y$ 已知数 $\{x_1,y_1,a,b\}$，方程 $ax+by=bx_1+(a \mod b)y_1$，则有关于 $x,y$ 的解多组.

那么考虑推导出限制 $x,y$ 的方程，使得未知数变得只有一组解。或者求出未知数的一组任意解，然后通过处理的方程将已知的 $x_i,y_i$ 变为 $x_0,y_0$. 考虑后者

根据模运算的意义：

\[a \mod b=a-\left\lfloor{\frac{a}{b}}\right\rfloor\times b \]

①式可化为$$ax+by=bx_1+(a-\left\lfloor{\frac{a}{b}}\right\rfloor\times b)y_1$$

\[ax+by=bx_1+ay_1-\left\lfloor{\frac{a}{b}}\right\rfloor\times b y_1 \]

\[ax+by=b(x_1-\left\lfloor{\frac{a}{b}}\right\rfloor y_1)+ay_1 \]

那么$x,y$必然有一组解

\[\begin{cases} x=y_1 \\ y=x1-\left\lfloor{\frac{a}{b}}\right\rfloor y_1 \end{cases} \]

接下来对比式

\[\begin{cases} ax+by\qquad \qquad \ \ \ =G \\ bx_1+(a \mod b)y_1=G \end{cases} \]

发现一式中的$a\rightarrow b,\ b\rightarrow (a \mod b)y_1$.
有一种辗转相除法的感觉？

推导出 $i$ 式与 $i-1$ 式的关系

\[ax_{i-1}+bx_{i-1}=G,\ bx_{i}+(a \mod b)y_i=G \]

\[a\rightarrow b, b\rightarrow (a \mod b) \]

若有 $a_n=G,\ b_n=0$ ，此时的 $a_n,b_n$ 即 $a,b$ 的一组解.

这时候我们考虑找到一组 $x_n,y_n$ 满足 $a_nx_n+b_ny_n$ ，为了求 $x$ 的最小整数解，另 $x_n=0$.

从上式的 $x_n$ 递归求出 $x$ 的解且满足 $x \in N^+$ 由于 $b_n$ 一定满足式 $b_n=0$ ，所以辅助未知数 $y_n$ 取什么都无所谓，以下令$y=0$.

答案的转化

这里的答案只是 $x$ 众多解其中的一个. 所以要继续处理 $x$.

设有辅助的数 $k \in N^+$ ，最终的解 $x_0=x-kb$.

那么 $x_0$ 直接 $x_0=(x\mod b +b) \mod b$.

短小精悍的代码
$\downarrow$

#include <bits/stdc++.h>
#define F(i,s,n) for(register int i=s;i<=n;++i)
#define ll long long
using namespace std;
ll a,b,x,y,ans,tmp;
void exgcd(ll a,ll b){
	if(!b){x=1,y=0;return;}
	exgcd(b,a%b);
	ll tmp=x;
	x=y;
	y=tmp-(a/b)*y;
}
int main(){
	cin>>a>>b;
	exgcd(a,b);
	x=(x%b+b)%b;
	cout<<x<<endl;
	return 0;
}