[编程笔记]-Linear_Congruence_Equation线性同余方程

概念

形如ax≡b(mod m)的方程

前置

[编程笔记]-Bezout’s_Lemma裴蜀定理
（乘法逆元页面尚未创建，可以去快速幂看看概念）
[编程笔记]-Extended_Euclidean_Algorithm拓展欧几里得算法

求解

乘法逆元

暂时没时间写，等把乘法逆元搞出来再写吧。

拓展欧几里得算法

线性同余方程等价于
ax=my+b(y∈Z)
ax-my=b

设y’=-y

ax+my’=b

根据裴蜀定理，对于任意不全为0的x、y，gcd(a,b)|ax+by

那么，只要gcd(a,m)|b，就一定有解；反之，则一定无解。

只要它有解，就可以用拓展欧几里得算法求出一个解，使ax+my’=gcd(a, m)=d，记作x₀、y₀

而只要把等式右边化作b即可，所以左右两边各乘b/d

(x₀*b/d)a+(y₀*b/d)m=b

这样就得到了一组x、y’的解。如果需要y取相反数即可。

例题

鉴于有些抽象，这里直接给出一道例题。
AcWing878-线性同余方程

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;

int n;
int a,b,m;

int exgcd(int a,int b,int &x,int &y){
    if(b==0){
        x=1;y=0;
        return a;
    }
    int d=exgcd(b,a%b,y,x);
    y-=a/b*x;
    return d;
}

int main(){
    cin.tie(0);
    cin>>n;
    while(n--){
        cin>>a>>b>>m;
        int x,y;
        int d=exgcd(a,m,x,y);
        if(b%d!=0)cout<<"impossible\n";
        else cout<<(ll)x*(b/d)%m<<endl;//题目要求在int范围内，所以直接%一个m就行，满足条件。
    }
    return 0;
}

完结撒花o(￣︶￣)o