同余方程乘法逆元扩展欧几里得算法

同余方程

给定整数$a,b,m$,求$ax\equiv b(\bmod m)$的一组解，不存在输出none 做法：将同余方程转化为不定方程：

1. $ax\equiv b(\bmod m)$等价于$ax=m(-y)+b$等价于$ax+my=b$
2. 由裴蜀定理知：当$gcd(a,m)|b$方程有解
3. 用扩展欧几里得算法求出$ax+my=gcd(a,m)$的解，再将解$x$乘以$\frac{b}{gcd(a,m)}$即可。

代码

#include <bits/stdc++.h>

using namespace std;

#define endl '\n'
#define debug(x) cout<<"a["<<x<<"]="<<a[x]<<endl;
#define pr(x) cout<<x<<endl;
#define IOS ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)

typedef long long LL;
typedef pair<int, int> PII;
const int INF = 0x3f3f3f3f;
const int N = 1e5 + 10;

int gcd(int a,int b){
    return b? gcd(b,a%b):a;
}

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

int main() {
    IOS;
#ifndef ONLINE_JUDGE
    freopen("/Users/houyunfei/CLionProjects/MyCppWorkSpace/test.in", "r", stdin);
    freopen("/Users/houyunfei/CLionProjects/MyCppWorkSpace/test.out", "w", stdout);
#endif
    int a,b,m,x,y;
    cin>>a>>b>>m;
    int d= exgcd(a,m,x,y);
    if (b%d==0){
        pr(1ll*x*b/d%m)
    }

    return 0;
}

乘法逆元

当$a$与$m$互质时，对于方程$ax\equiv 1(\bmod m)$求$a$当乘法逆元$x(0<x<m)$ 做法：

1. 将方程变形为：$ax+my=1$
2. 使用扩展欧几里得算法求$ax+my=gcd(a,m)$的一组解$x$，
3. 原方程的解为：$(x \% m+m) \% m$

#include <bits/stdc++.h>

using namespace std;

#define endl '\n'
#define debug(x) cout<<"a["<<x<<"]="<<a[x]<<endl;
#define pr(x) cout<<x<<endl;
#define IOS ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)

typedef long long LL;
typedef pair<int, int> PII;
const int INF = 0x3f3f3f3f;
const int N = 1e5 + 10;

int gcd(int a,int b){
    return b? gcd(b,a%b):a;
}

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


int main() {
    IOS;
#ifndef ONLINE_JUDGE
    freopen("/Users/houyunfei/CLionProjects/MyCppWorkSpace/test.in", "r", stdin);
    freopen("/Users/houyunfei/CLionProjects/MyCppWorkSpace/test.out", "w", stdout);
#endif
    int a,m,x,y;
    cin>>a>>m;
    exgcd(a,m,x,y);
    pr((x%m+m)%m)

    return 0;
}