线性同余方程

8.线性同余方程

\(ax\equiv{b}(mod\,m)\)

\(x\)的解分为无解，有有限个解的情况

记\(gcd(a,m)=d\)

当\(d\nmid{b}\)时，无解（因为d整除左边而不整除右边）

当\(d\mid{b}\)时，有解。此时考虑\(ax_0+mk_0={gcd(a,m)}\)的解，左右同除以d乘以b，得

\(\frac{abx_0}{d}+\frac{mbk_0}{d}=b\)

故最后\(x=\frac{bx_0}{d}\)

我们要得到所有满足的\(x\)，可以考虑先找到最小的，然后算出所有的。

\(x_i=x_{min}+i*\frac{m}{d}\)

故\(x_{min}=(x\,mod\,\frac{m}{d}+\frac{m}{d})\,mod\,\frac{m}{d}\)

代码如下

#include <bits/stdc++.h>

using namespace std;

#define int long long

int exgcd(int a,int b,int& x,int& y){
    int x1=1,x2=0,x3=0,x4=1;
    while(b){
        int c=a/b;
        tie(a,b,x1,x2,x3,x4)=make_tuple(b,a-c*b,x3,x4,x1-c*x3,x2-c*x4);
    }
    x=x1,y=x2;
    return a;
}

bool liEu(int a, int b, int c, int& x, int& y) {
    int d=exgcd(a,b,x,y);
    if(c%d!=0)return 0;
    int k =c/d;
    x*=k;
    y*=k;
    return 1;
}

signed main(){
    int a,b,x,y,c;
    int _x[100];
    // cin>>a>>b>>c;
    cin>>a>>b;c=1;//c=1等价求逆元
    int d=exgcd(a,b,x,y);
    if(liEu(a,b,c,x,y)){
        _x[0]=(x%(b/d)+b/d)%(b/d);
        // for(int i=1;i<d;++i){
        //     _x[i]=_x[i-1]+b/d;
        // }
    }
    // for(int i=0;i<d;++i){
    //     cout<<_x[i]<<endl;
    // }
    cout<<_x[0]<<endl;
}