AcWing 878. 线性同余方程（拓展欧几里得）

题目链接

https://www.acwing.com/problem/content/880/

思路

a i × x i ≡ b i ( m o d   m i ) a_i\times x_i≡b_i(mod \ m_i) ai​×xi​≡bi​(mod mi​)我们可以将右边变一下形， a i × x i ≡ c i × m i + b i ( m o d   m i ) a_i\times x_i≡c_i \times m_i + b_i(mod \ m_i) ai​×xi​≡ci​×mi​+bi​(mod mi​) 然后移向过来就是个一个贝祖定理的形式了 a i × x i + c i × m i ≡ b i ( m o d   m i ) a_i\times x_i + c_i \times m_i≡ b_i(mod \ m_i) ai​×xi​+ci​×mi​≡bi​(mod mi​)，那么我们只需要判断 g c d ( a i , m i ) gcd(a_i,m_i) gcd(ai​,mi​)是否为b的倍数即可，如果不是b的倍数，那么说明不存在这样的等式，否则我们就通过拓展欧几里得计算可行值，注意的是这里要求的是在int范围内，所以我们最后需要对我们算的这个可性值取模，即： ( x × b d ) m o d   m (x \times \frac{b}{d}) mod \ m (x×db​)mod m

代码

#include 
using namespace std;

#define ll long long

ll exgcd(ll a,ll b,ll &x,ll & y){
    if(!b){
        x = 1,y = 0;
        return a;
    }
    ll d = exgcd(b,a%b,y,x);
    y -= a / b * x;
    return d;
}
//a*x + m*y = b
int main()
{
    int n;
    scanf("%d",&n);
    while(n--){
        ll a,b,m,x,y;
        scanf("%lld%lld%lld",&a,&b,&m);
        ll d = exgcd(a,m,x,y);
        if(b % d) 
            printf("impossible\n");
        else
            printf("%lld\n",((b/d) * x) % m);
    }
    return 0;
}