题解 | #【模板】非质模数下的乘法逆元#

题目链接

【模板】非质模数下的乘法逆元

题目描述

给定若干组正整数对，每组为两个整数 $a, m$ ，要求计算乘法逆元，即找到满足

a\cdot x \equiv 1\pmod{m}

的最小非负整数 $x$ 。注意： $m$ 不保证为质数。

解题思路

判定存在性：当且仅当 $\gcd(a, m) = 1$ 时， $a$ 在模 $m$ 意义下存在逆元。
方法一（推荐，扩展欧几里得）：利用扩展欧几里得算法求解整数 $x, y$ 使
$a\cdot x + m\cdot y = \gcd(a, m).$
若 $\gcd(a, m)=1$ ，则上式化为 $a\cdot x + m\cdot y = 1$ ，两边对 $m$ 取模可得 $a\cdot x \equiv 1\pmod{m}$ ，因此 $x$ 对 $m$ 取非负最小剩余即可作为逆元： $x' = (x\bmod m + m)\bmod m$ 。
方法二（了解）：若 $\gcd(a,m)=1$ ，也可用欧拉定理 $a^{\varphi(m)} \equiv 1\pmod m$ 得 $a^{\varphi(m)-1}$ 为逆元，但需要分解 $m$ 求 $\varphi(m)$ ，整体不如扩欧稳定简洁。
边界与细节：
- 若 $\gcd(a,m)\ne 1$ ，逆元不存在；通常输出 $-1$ （如评测无特例声明）。
- 计算中注意将结果规范到 $[0, m-1]$ ： $x' = (x\bmod m + m)\bmod m$ 。
复杂度：扩展欧几里得为 $\mathcal{O}(\log \min(a,m))$ ，空间 $\mathcal{O}(1)$ 。

代码

c++
java
python

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

// 扩展欧几里得：返回 gcd(a,b)，并求出 ax + by = gcd(a,b) 的一组 (x, y)
static inline long long exgcd(long long a, long long b, long long &x, long long &y) {
    if (b == 0) { x = 1; y = 0; return a; }
    long long x1, y1;
    long long g = exgcd(b, a % b, x1, y1);
    x = y1;
    y = x1 - (a / b) * y1;
    return g;
}

// 计算 a 在模 m 下的乘法逆元；若不存在返回 -1
static inline long long modInverse(long long a, long long m) {
    long long x, y;
    long long g = exgcd(a, m, x, y);
    if (g != 1) return -1;               // 不互质，无逆元
    long long inv = (x % m + m) % m;     // 规范到 [0, m-1]
    return inv;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int T; // 测试组数
    if (!(cin >> T)) return 0;
    while (T--) {
        long long a, m;
        cin >> a >> m;
        cout << modInverse(a, m) << '\n';
    }
    return 0;
}

import java.util.*;

public class Main {
    // 扩展欧几里得：返回 gcd(a,b)，并求 ax + by = gcd(a,b)
    static long exgcd(long a, long b, long[] xy) {
        if (b == 0) {
            xy[0] = 1; // x
            xy[1] = 0; // y
            return a;
        }
        long[] nxt = new long[2];
        long g = exgcd(b, a % b, nxt);
        xy[0] = nxt[1];
        xy[1] = nxt[0] - (a / b) * nxt[1];
        return g;
    }

    // 计算 a 在模 m 下的乘法逆元；若不存在返回 -1
    static long modInverse(long a, long m) {
        long[] xy = new long[2];
        long g = exgcd(a, m, xy);
        if (g != 1) return -1; // 不互质，无逆元
        long x = xy[0];
        long inv = (x % m + m) % m; // 规范到 [0, m-1]
        return inv;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int T = sc.nextInt();
        while (T-- > 0) {
            long a = sc.nextLong();
            long m = sc.nextLong();
            System.out.println(modInverse(a, m));
        }
    }
}

# 扩展欧几里得：返回 (g, x, y)，满足 a*x + b*y = g = gcd(a, b)
def exgcd(a: int, b: int):
    if b == 0:
        return a, 1, 0
    g, x1, y1 = exgcd(b, a % b)
    x = y1
    y = x1 - (a // b) * y1
    return g, x, y


# 计算 a 在模 m 下的乘法逆元；若不存在返回 -1
def mod_inverse(a: int, m: int) -> int:
    g, x, _ = exgcd(a, m)
    if g != 1:
        return -1
    return (x % m + m) % m


T = int(input())
for _ in range(T):
    a_str = input().strip()
    while a_str == "":
        a_str = input().strip()
    a, m = map(int, a_str.split())
    print(mod_inverse(a, m))

算法及复杂度

算法：扩展欧几里得，解 $a\cdot x + m\cdot y = \gcd(a,m)$ ；若 $\gcd(a,m)=1$ ，取 $x$ 的非负最小剩余为逆元。
时间复杂度： $\mathcal{O}(\log \min(a,m))$ 。
空间复杂度： $\mathcal{O}(1)$ 。