AcWing 876. 快速幂求逆元

◎

本节目标

在质数模数下用费马小定理计算乘法逆元。

题意与约束

给定 a 和题目保证为质数的 p，其中 p≤2×10^9，输出 a 在模 p 下的逆元；若不存在则输出 impossible。

第一反应与瓶颈

普通除法不能直接搬进模运算：a / b mod p 不是先做整数除法。逐个尝试所有余数寻找 x 使 a·x ≡ 1 也需要线性时间。

数学关系与算法推导

当 p 是质数且 a mod p ≠ 0 时，费马小定理给出 a^(p-1) ≡ 1，因此 a^(p-2) 就是逆元。用快速幂在 O(log p) 时间计算；余数为零时没有逆元。

正确性依据

可逆条件满足时，a · a^(p-2) = a^(p-1) ≡ 1 (mod p)，返回值定义上就是逆元。余数为零时任意乘积仍为零，不可能同余于一。

样例执行过程

4 mod 3 = 1，逆元为 1。6 mod 3 = 0，无论乘什么都不能得到 1，输出 impossible。

代码实现

C++

C++17

#include <iostream>
using namespace std;

long long powerModulo(long long base, long long exponent, long long modulus) {
    long long result = 1;
    base %= modulus;
    while (exponent > 0) {
        if ((exponent & 1) != 0) {
            result = result * base % modulus;
        }
        base = base * base % modulus;
        exponent >>= 1;
    }
    return result;
}

long long modularInverse(long long value, long long prime) {
    if (prime <= 1) {
        return -1;
    }
    value %= prime;
    if (value < 0) {
        value += prime;
    }
    if (value == 0) {
        return -1;
    }
    return powerModulo(value, prime - 2, prime);
}

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

    int count;
    cin >> count;
    while (count-- > 0) {
        long long value, prime;
        cin >> value >> prime;
        long long inverse = modularInverse(value, prime);
        if (inverse == -1) {
            cout << "impossible\n";
        } else {
            cout << inverse << '\n';
        }
    }
    return 0;
}
#endif

Python

Python 3

import sys


def power_modulo(base: int, exponent: int, modulus: int) -> int:
    result = 1
    base %= modulus
    while exponent > 0:
        if exponent & 1:
            result = result * base % modulus
        base = base * base % modulus
        exponent >>= 1
    return result


def modular_inverse(value: int, prime: int) -> int:
    if prime <= 1:
        return -1
    value %= prime
    if value == 0:
        return -1
    return power_modulo(value, prime - 2, prime)


def main() -> None:
    data = list(map(int, sys.stdin.buffer.read().split()))
    answers = []
    for index in range(1, len(data), 2):
        inverse = modular_inverse(data[index], data[index + 1])
        answers.append(str(inverse) if inverse != -1 else 'impossible')
    print('\n'.join(answers))


if __name__ == '__main__':
    main()

复杂度分析

每组时间 O(log p)，额外空间 O(1)。

边界与易错点

费马公式不是任意模数下的万能公式；这里依赖题目给出的质数模数，并先判断 a % p 是否为零。取模后的两个乘数都小于 2×10^9，故标准 C++17 的 long long 可安全保存中间乘积；更大模数需改用可移植模乘。核心函数用 -1 表示不存在，入口再转换为平台要求的 impossible。

模式迁移

模数是质数且分母非零时，组合数中的除法也可改写为乘逆元。回到欧拉函数与模运算。