exgcd+乘法逆元相关笔记

#include <iostream>
#include <cstdio>
using namespace std;
const int pass=0;

//exgcd:

//求解二元一次不定方程
//ax+by=(a,b)=(b,a%b)=bx'+(a%b)*y'=bx'+(a-b*(a/b))*y'=b*(x'-(a/b)*y')+ay'
//则有 y=(x'-(a/b)*y'),x=y'

//不断嵌套
//不断递归，直到b=0;有解x=1，y=0

//求逆元：逆元符号:#
//ax#1(mod b)
//x为逆元
//ax+kb=1
//然后用exgcd求

int n,x,y,temp;

int exgcd(int a,int b,int &x,int &y){
if(b==0){
x=1;y=0;
return a;
}
int t=exgcd(b,a%b,x,y);
int tx=x,ty=y;
x=ty;y=(tx-(a/b)*ty);
return t;
}
int gcd(int a,int b){
if(a%b==0) return b;
return gcd(b,a%b);
}

int main(){
//求a/b%p
int a,b,c;
scanf("%d %d %d",&a,&b,&c);
int d=exgcd(a,c,x,y);
cout<<x<<endl;
x=x*(1/d);
cout<<x<<endl<<d<<endl;;
cout<<b*x%c<<endl;
}