【NOIP2012 提高组 day2】同余方程
题解:
用裴蜀定理就OK,是一道裸的gcd;
#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll a,b,x,y;
ll read(){
ll num=0;
char ch=getchar();
while(ch>'9'||ch<'0'){
ch=getchar();
}
while(ch<='9'&&ch>='0'){
num=(num<<3)+(num<<1)+ch-'0';
ch=getchar();
}
return num;
}
ll gcd(ll xa,ll xb,ll & x,ll & y){
if(!xb){
x=1,y=0;
return xa;
}
ll d=gcd(xb,xa%xb,x,y);
ll z=x;
x=y;
y=z-y*(xa/xb);
return d;
}
int main(){
a=read();
b=read();
gcd(a,b,x,y);
cout<<(x%b+b)%b;
}