一元一次同余方程例题_同余方程化简

#include<cstdio>
#include<cmath>
#define ll long long
using namespace std;
int e_gcd(int a,int b,int &x,int &y){
    if(b==0){
        x=1;y=0;
        return a;
    }
    int ans=e_gcd(b,a%b,x,y);
    int temp=x;
    x=y;
    y=temp-a/b*y;
    return ans;
}
int main(){
    int x,y,a,b;
    freopen("mod.in","r",stdin);
    freopen("mod.out","w",stdout);
    scanf("%d%d",&a,&b);
    e_gcd(a,b,x,y);
    //printf("%d %d",x,y);
    x=x%b;
    if(x<0) x+=b;
    printf("%d",x);
    return 0;
}