题解 P1082【同余方程】

0.前言

笑死直接代码

1.正文

#include <cstdio>int a,b,x,y,k;void exgcd(int a,int b) {
    if (!b) {
    x=1;y=0;return;}exgcd(b,a%b);k=x;x=y;y=k-a/b*y;return;
}int main() {
    scanf("%d %d",&a,&b);exgcd(a,b);printf("%d",(x+b)%b);return 0;
}