同余方程

冥诺在线发呆 · 2019-07-02 16:10:30 · 个人记录

第一题：【模板】同余方程

洛谷题目链接 *题意：求关于x的同余方程 ax≡1(mod b)的最小正整数解。**

*思路：ax≡b(mod m)等价于ax-b是m的倍数，设为-y倍，则可以改写为am+my=b。ax≡1(mod b)有解当且仅当gcd(a,b)=1，则可改写为ax+by=1,由欧几里德算法得到一组特解x,y,则通解为所有模b与x同余的整数**

typedef long long ll;
ll x,y;
void exgcd(ll a,ll b,ll &d,ll &x,ll &y){//d为gcd(a,b)
    if(!b){ 
        x=1;y=0;d=a;//得到一组特解
        return ;
    }
    exgcd(b,a%b,d,y,x);
    y=y-a/b*x;
}
int main() {
    ll a=read(),b=read(),d;//输入a,b
    exgcd(a,b,d,x,y);//同余方程
    printf("%lld\n",(x%b+b)%b);//输出解
    return 0;
}