逆元的求解

使用拓展欧几里得算法求解，使用条件是 g c d ( a , m ) = 1 gcd(a,m)=1 gcd(a,m)=1。

int inverse(int a, int m) {
    int x, y;
    int g = exGcd(a, m, x, y); //求解ax+my=1;
    return (x % m + m) % m; // a模m的逆元为(x%m+m)%m
}

若 m m m是素数，且 a a a不是 m m m的倍数，则可以使用费马小定理求解逆元。

费马小定理

设 m m m是素数， a a a是任意整数且 a ≢ 0 ( m o d    m ) a≢0(mod\;m) a≢0(modm)，则 a m − 1 ≡ 1 ( m o d    m ) a^{m-1}≡1(mod\; m) am−1≡1(modm)。

由 a m − 1 ≡ 1 ( m o d    m ) a^{m-1}≡1(mod\; m) am−1≡1(modm)知 a ∗ a m − 2 ≡ 1 ( m o d    m ) a*a^{m-2}≡1(mod\; m) a∗am−2≡1(modm)，由逆元定义知 a m − 2 % m a^{m-2}\%m am−2%m就是 a a a模 m m m的逆元，通过快速幂来求解。

#include <cstdio>
#include <cmath>

int exGcd(int a, int b, int &x, int &y) { //x和y的引用
    if (b == 0) { //b为0时，a为gcd，则a*1+b*0=gcd
        x = 1;
        y = 0;
        return a;
    }
    int g = exGcd(b, a % b, x, y); //递归计算exGcd(b,a%b)
    int temp = x; //存放x的值
    x = y; //更新x=y(old)
    y = temp - a / b * y;
    return g; //g是gcd
}

int inverse(int a, int m) {
    int x, y;
    int g = exGcd(a, m, x, y); //求解ax+my=1;
    return (x % m + m) % m; // a模m的逆元为(x%m+m)%m
}

typedef long long LL;
//求a^b%m，递归写法
//若初始时a大于m，则在进入函数前先让a对m取模
LL BinaryPow(LL a, LL b, LL m) {
    if (b == 0) return 1;
    // b为奇数，转换为b-1
    if (b % 2 == 1) { //可用if (b & 1)替代
        return a * BinaryPow(a, b - 1, m) % m;
    } else { // b为偶数，转换为b/2
        LL mul = BinaryPow(a, b / 2, m);
        return mul * mul % m;
    }
}

bool isPrime(int n) {
    if (n <= 1) return false;
    int sqr = (int)sqrt(1.0 * n);
    //如果n没有接近int型变量的范围上界，可以写i*i<=n
    for (int i = 2; i <= sqr; i++) { //遍历2~根号n
        if (n % i == 0) return false;
    }
    return true;
}

int main() {
    int a, m, b;
    scanf("%d %d", &a, &m);
    if (isPrime(m) && a % m != 0) { //使用费马小定理
        a %= m;
        b = (int)BinaryPow((LL)a, (LL)(m - 2), (LL)m);
    } else {
        b = inverse(a, m);
    }
    printf("逆元b=%d", b);
    return 0;
}