- 2022tysc0158 的博客
【模板】扩展欧几里得算法求乘法逆元
- 2023-11-15 7:25:19 @
#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));
}