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

题目链接

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

题目描述

给定正整数对 $(a, p)$ ，求 $a$ 模 $p$ 的乘法逆元。

需要注意的是，数据不保证 $p$ 为质数。

解题思路

本题要求解线性同余方程 $ax \equiv 1 \pmod{p}$ ，其中 $x$ 就是 $a$ 模 $p$ 的乘法逆元。题目特别指出， $p$ 不一定是质数，这意味着我们不能使用费马小定理。

求解该方程的通用方法是使用 扩展欧几里得算法（Extended Euclidean Algorithm）。

问题转化
- 线性同余方程 $ax \equiv 1 \pmod{p}$ 可以等价地写成二元一次不定方程（丢番图方程）的形式： $ax + py = 1$ ，其中 $y$ 是一个整数。
- 根据 裴蜀定理，这个方程有解的充要条件是 $\gcd(a, p)$ 能够整除 $1$ 。因为 $a$ 和 $p$ 都是正整数，所以这个条件就是 $\gcd(a, p) = 1$ 。即 $a$ 和 $p$ 必须互质。
扩展欧几里得算法
- 扩展欧几里得算法是用来求解形如 $ax + by = \gcd(a, b)$ 的方程的一组整数解 $(x, y)$ 的。
- 对于本题，我们调用扩展欧几里得算法求解 $ax + py = \gcd(a, p)$ 。由于逆元存在的前提是 $\gcd(a, p) = 1$ ，所以该算法实际上就是求解 $ax + py = 1$ 。
- 算法会返回一组解 $(x, y)$ 。其中 $x$ 就是我们要求的 $a$ 模 $p$ 的一个乘法逆元。
结果处理
- 扩展欧几里得算法求出的解 $x$ 可能是一个负数或大于 $p$ 的数。
- 为了得到最小的正整数解，我们需要将其转化到 $[1, p-1]$ 的范围内。通用的转化公式是 (x % p + p) % p。这样可以确保无论 $x$ 是正还是负，结果都是一个落在 $[0, p-1]$ 范围内的正数。

综上，我们通过扩展欧几里得算法求解即可。该算法的复杂度为 $O(\log p)$ 。

代码

c++
java
python

#include <iostream>

using namespace std;
using ll = long long;

// 扩展欧几里得算法，求解 ax + by = gcd(a, b)
ll exgcd(ll a, ll b, ll &x, ll &y) {
    if (b == 0) {
        x = 1;
        y = 0;
        return a;
    }
    ll d = exgcd(b, a % b, y, x);
    y -= (a / b) * x;
    return d;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t;
    cin >> t;
    while (t--) {
        ll a, p;
        cin >> a >> p;
        ll x, y;
        exgcd(a, p, x, y);
        // 保证结果是最小正整数
        cout << (x % p + p) % p << "\n";
    }
    return 0;
}

import java.util.Scanner;

public class Main {
    // 扩展欧几里得算法，返回 {gcd(a, b), x, y}
    public static long[] exgcd(long a, long b) {
        if (b == 0) {
            return new long[]{a, 1, 0};
        }
        long[] res = exgcd(b, a % b);
        long d = res[0];
        long x = res[2];
        long y = res[1] - (a / b) * res[2];
        return new long[]{d, x, y};
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int t = sc.nextInt();
        while (t-- > 0) {
            long a = sc.nextLong();
            long p = sc.nextLong();
            long[] result = exgcd(a, p);
            long x = result[1];
            // 保证结果是最小正整数
            System.out.println((x % p + p) % p);
        }
    }
}

def exgcd(a, b):
    """扩展欧几里得算法，返回 (gcd(a, b), x, y)"""
    if b == 0:
        return a, 1, 0
    d, y, x = exgcd(b, a % b)
    y -= (a // b) * x
    return d, x, y

def main():
    t = int(input())
    for _ in range(t):
        a, p = map(int, input().split())
        gcd, x, y = exgcd(a, p)
        # 保证结果是最小正整数
        print((x % p + p) % p)

if __name__ == "__main__":
    main()

算法及复杂度

算法：扩展欧几里得算法
时间复杂度：对于每次查询，时间复杂度为 $O(\log p)$ 。
空间复杂度： $O(\log p)$ ，来自于递归的栈深度。