思路讲解
拓展欧几里得算法
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
线性同余方程 $ax=b \ (mod \ n) 的意思是指(ax)\ mod \ n=b$ x为未知数
那这个线性同余方程方程可以转换为什么方便我们求解那？
a∗x=1(mod b)的成立条件是gcd(a,b)∣1 (a，b的最大公约数整除1) 当然，这是一定有解的，除非a,b中有一个为0。
AC代码
x∗y=1(mod p) −>x_∗y+y_∗p=gcd(y,p)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
| #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;
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;
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……）
需要加一个这个判断是否存在逆元
1
2
3
4
| 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。