数学上的乘法逆元就是倒数，即 $a$ 的逆元是 $\dfrac{1}{a}$（或 $a^{-1}$），也即与 $a$ 相乘得 $1$ 的数。若 $ax=1$，则 $x$ 是 $a$ 的乘法逆元。

这里我们讨论关于取模运算的乘法逆元，即对于整数 $a$，与 $a$ 互质的数 $b$ 作为模数，当整数 $x$ 满足 $ax \mod b≡1$ 时，称 $x$ 为 $a$ 关于模 $b$ 的逆元，代码表示就是 a * x % b == 1。

在算法竞赛中，经常会遇到求解数据很大，则输出模 $10^9+7$ 的解这类要求。加法、减法、乘法等操作，基于同余理论直接取模即可。但遇到除法时，某步中间结果不一定能完成整除，就无法求解了。

举个例子：求 $\dfrac{3\times 6}{3}$ 对 $7$ 取模的结果。我们直接算出 $\dfrac{3\times 6}{3}$ 的结果是 $6$，对 $7$ 取模得最终答案是 $6$。

但我们通常面对的问题是中间结果超过long long甚至int的范围，而不得不在每一步基于同余理论取模，我们用这个例子尝试一下：

还是求 $\dfrac{3\times 6}{3}$

1. $3\times 6=18$
2. $18\mod 7=4$
3. $4$ 这个中间结果再做 $\dfrac{4}{3}$ 无法整除，就无法进行下去了。

但我们可以求出除数 $3$ 关于模数 $7$ 的逆元 $5$（根据逆元定义，$5$ 符合 $3\times 5 \mod 7=1$），从而，用乘以 $5$ 代替除以 $3$。

上述第二步除法变乘法：$4\times 5=20$，$20 \mod 7=6$

从而也计算出了正确的结果 $6$。

乘法逆元的作用就是：

设 $m$ 是一个天文数字，$a$、$b$ 已知，预期要计算（假设答案为 $c$）$\dfrac{m}{a}\mod b$

对于 $a$ 的逆元 $d$，能够满足

$m\times d\mod b=\dfrac{m}{a}\mod b=c$

在有些问题中，无法计算最终值很大的 $m$，只能得到基于同余的一个中间值 $m\mod b=e$ 来计算 $\dfrac{e}{a}\mod b$，而 $e$ 可能无法整除 $a$，就可以用 $a$ 的逆元 $d$，来计算 $e\times d\mod b$。

故而我们需要一个算法求除数的取模逆元，从而在四则运算取模的任务中，用逆元将除法转为乘法。

#include<cstdio>
using namespace std;
void exgcd(int a,int b,int &x,int &y){
	if(b==0){x=1,y=0;return;}
	exgcd(b,a%b,y,x);
	y-=(a/b)*x;
}
int get_inv(int a,int p){
	int x=1,y=0;
	exgcd(a,p,x,y);//x=a_inv,a*a_inv+p*y=1
	return (x%p+p)%p;
}
int a,p;
int main(){
	scanf("%d%d",&a,&p);
	printf("%d",get_inv(a,p));
}

---

以下copy自百度百科（6

乘法逆元，是指数学领域群 $G$ 中任意一个元素 $a$，都在 $G$ 中有唯一的逆元 $a'$，具有性质 $a×a'=a'×a=e$，其中 $e$ 为该群的单位元。

例如：$4$ 关于 $1$ 模 $7$ 的乘法逆元为多少？

$4x≡1\mod7$

这个方程等价于求一个 $x$ 和 $k$，满足

$4x=7k+1$

其中 $x$ 和 $k$ 都是整数。

若 $ax≡1\mod f$， 则称 $a$ 关于 $1$ 模 $f$ 的乘法逆元为 $x$。也可表示为 $ax≡1(\mod f)$。

当 $a$ 与 $f$ 互素时，$a$ 关于模 $f$ 的乘法逆元有解。如果不互素，则无解。如果 $f$ 为素数，则从 $1$ 到 $f-1$ 的任意数都与 $f$ 互素，即在 $1$ 到 $f-1$ 之间都恰好有一个关于模 $f$ 的乘法逆元。

例如，求 $5$ 关于模 $14$ 的乘法逆元：

$14=5×2+4$

$5=4×$$1+1$

说明 $5$ 与 $14$ 互素，存在 $5$ 关于 $14$ 的乘法逆元。

$1=5-4=5-(14-5×2)=5×3-14$

因此，$5$ 关于模 $14$ 的乘法逆元为 $3$。

乘法逆元的定义及用途，以及求逆元的三种算法：扩展欧几里得、费马小定理、递推求逆元。

---

• P类问题：存在多项式时间算法的问题,即在多项式时间内可解的问题

  例如：冒泡排序,快速排序等问题

• NP类问题：能在多项式时间内验证出一个正确解的问题，也就是说这个问题不一定在多项式时间内可解,但可以在多项式时间内验证

  例如：大数分解问题,比如 $180576$ 这个数让你拆成两个数相乘,必须是三位乘以三位的,可能很久都解不出来(如果是一个很大很大的数的话),但是我告诉你这是 $352\times 513$ 得到的,那么很简单就能在多项式时间内验证是否正确,这就是NP问题

• NPC类问题：存在这样一个NP问题，所有的NP问题都可以约化成它

• NP-Hard类问题：所有的NP问题都可以约化成它

c的