[NOIp2012提高组]同余方程

时间:2021-08-10 15:26:57

OJ题号:

洛谷1082

思路:

逆元模板。

 #include<cstdio>
#include<cctype>
inline int getint() {
char ch;
while(!isdigit(ch=getchar()));
int x=ch^'';
while(isdigit(ch=getchar())) x=(((x<<)+x)<<)+(ch^'');
return x;
}
int exgcd(const int a,const int b,int &x,int &y) {
if(!b) {
x=;
y=;
return a;
}
int d=exgcd(b,a%b,y,x);
y-=a/b*x;
return d;
}
int main() {
int a=getint(),b=getint();
int x,y;
exgcd(a,b,x,y);
printf("%d\n",(x+b)%b);
return ;
}