A Number Theoretical Problem（乘法逆元模版问题） · znzryb

## 思路讲解

拓展欧几里得算法

[https://www.bilibili.com/video/BV1rD4y1C7qg/?spm_id_from=333.337.search-card.all.click&vd_source=4350e5f2584d2f27c848b347ea11b675](https://www.bilibili.com/video/BV1rD4y1C7qg/?spm_id_from=333.337.search-card.all.click&vd_source=4350e5f2584d2f27c848b347ea11b675)

这篇题解非常好

[https://www.luogu.com.cn/article/1wawrmip](https://www.luogu.com.cn/article/1wawrmip)

线性同余方程 $a*x=b \ (mod \ n) $的意思是指$(a*x)\ mod \  n=b$   x为未知数  

![image](https://media.znzryb.com/20241203-30d0ac32/image_110a42b1.png)

那这个线性同余方程方程可以转换为什么方便我们求解那？

![image](https://media.znzryb.com/20241203-30d0ac32/image_ef29034b.png)

$a*x=1(mod\ b)$的成立条件是$gcd(a,b)|1\ (a，b的最大公约数整除1)$  当然，这是一定有解的，除非a,b中有一个为0。

![这个是对这一问题转化的感性理解](https://media.znzryb.com/20241203-30d0ac32/image_bc517ae4.png)

## AC代码

$x*y=1(mod\ p) \ -> x\_*y+y\_*p=gcd(y,p)$

```cpp
#include <iostream>
#include <cstring>
#include <algorithm>
#include <deque>
#include <queue>
#include <vector>
#include <set>
#include <map>
#include <cmath>
#include <bitset>
#include <iterator>
#include <random>
#include <iomanip>

using namespace std;
typedef long long ll;
const ll N=static_cast<ll>(2e5)+10;
ll n,T;
// https://ac.nowcoder.com/acm/contest/5891/B
void exgcd(ll a,ll b,ll &x,ll &y){
	if(!b)
		x=1,y=0;
	else
		exgcd(b, a%b, y, x),y-=a/b*x;
}
ll gcd(ll a,ll b){
	if(b==0)
		return a;
	return gcd(b,a%b);
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	cin>>T;
	while (T--) {
		ll y,p;
		cin>>y>>p;
		// x*y=1(mod p) -> x_*y+y_*p=gcd(y,p)
		if(gcd(y,p)!=1){
			cout<<-1<<endl;
			continue;
		}
		ll x_,y_;
		exgcd(y, p, x_, y_);
		cout<<(x_+p)%p<<endl;
	}
	return 0;
}
```

## 心路历程（WA，TLE，MLE……）

需要加一个这个判断是否存在逆元

```cpp
if(gcd(y,p)!=1){
			cout<<-1<<endl;
			continue;
		}
```

$(x*y)\ mod\ p=1\ ->(x\ mod\ p)*(y\ mod\ p)=1$

所以说$y\ mod\ p=1$才有可能求出逆元$x$。