【题解】Luogu P1082【同余方程】

分析

就是求一个线性同余,套一个exgcd就好了

代码

#include<cstdio>
int exgcd(int a,int b,int &x,int &y){
    if(b == 0){x = 1;y = 0;return a;}
    int d = exgcd(b,a % b,x,y);
    int z = x;x = y;y = z - y * (a / b);
    return d;
}

int main(){
    int a,b,x,y;scanf("%d %d",&a,&b);
    int d = exgcd(a,b,x,y);
    int u0 = 1 * x / d;
    printf("%d\n",(x % b + b) % b);

    return 0;
}