单变元模线性方程

说明

已知a,b,n, 求x, 使得 ax ≡ b(mod n)

输入a,b,n 输出所有[0, n)中的解(个数为gcd(a,n))

要注意在处理过程中,如果 b 是负数,需要转换:b = ((b % n) + n) % n;

复杂度:O(logN)

使用方法

  • vector<ll> ans = line_mod_equation(a, b, n);

模版

ll ex_gcd(ll a,ll b,ll &x,ll &y){
    if (b==0) {
        x=1,y=0;
        return a;
    }
    else{
        ll r=ex_gcd(b,a%b,y,x);
        y-=x*(a/b);
        return r;
    }
}
vector<ll> line_mod_equation(ll a, ll b, ll n) {
    ll x, y;
    ll d = extend_gcd(a, n, x, y);
    vector<ll> ans;
    ans.clear();
    if (b % d == 0) {
        x = (x % n + n) % n;
        x %= (n / d);
        ans.push_back(x * (b / d) % (n / d));
        for (ll i = 1; i < d; i++) ans.push_back((ans[0] + i * n / d) % n);
    }
    return ans;
}

results matching ""

    No results matching ""