题解 | #【模板】分数取模#

题目链接

题目描述

给定 $T$ 组数据，每组数据包含两个整数 $a, b$ 。求 $a \cdot b^{-1} \pmod{10^9 + 7}$ 的值。其中 $b^{-1}$ 表示 $b$ 在模 $10^9+7$ 意义下的逆元。

输入描述: 第一行一个整数 $T$ ，表示数据组数。接下来 $T$ 行，每行两个整数 $a, b$ 。

输出描述: 对于每组数据，输出一行，表示 $a \cdot b^{-1} \pmod{10^9+7}$ 的结果。

解题思路

本题的核心是计算 $\frac{a}{b} \pmod p$ ，其中 $p = 10^9 + 7$ 是一个质数。在模算术中，除法被定义为乘以其 模乘法逆元。即： $a / b \pmod p \equiv a \cdot b^{-1} \pmod p$ 其中 $b^{-1}$ 是 $b$ 的模逆元，满足 $(b \cdot b^{-1}) \equiv 1 \pmod p$ 。

如何求模逆元？

当模数 $p$ 是一个质数时（本题的 $10^9+7$ 就是质数），我们可以使用 费马小定理 (Fermat's Little Theorem)。

费马小定理：如果 $p$ 是一个质数，对于任意一个整数 $b$ 且 $b \not\equiv 0 \pmod p$ ，都有： $b^{p-1} \equiv 1 \pmod p$

对这个式子两边同时乘以 $b^{-1}$ ，可以得到： $b^{p-1} \cdot b^{-1} \equiv 1 \cdot b^{-1} \pmod p$ $b^{p-2} \equiv b^{-1} \pmod p$

这个结论给了我们一个直接的计算方法： $b$ 在模 $p$ 下的逆元就是 $b^{p-2} \pmod p$ 。

算法步骤

对于每组输入的 $a$ 和 $b$ ，以及固定的质数模 $p = 10^9 + 7$ 。
我们需要计算 $(a \cdot b^{p-2}) \pmod p$ 。
计算 $b^{p-2} \pmod p$ 可以使用 快速幂算法，这在 HIGH16 中已经作为模板实现。
将 $a$ 和计算出的 $b$ 的逆元相乘，再对 $p$ 取模，得到最终结果。
注意处理 $a$ 可能为负数的情况，可以用 (a % p + p) % p 将其映射到正数域。

最终的计算公式为： result = ((a % p + p) % p * power(b, p - 2, p)) % p

代码

cpp
java
python

#include <iostream>

using namespace std;

const int p = 1000000007;

long long power(long long base, long long exp, long long mod) {
    long long res = 1 % mod;
    base %= mod;
    while (exp > 0) {
        if (exp % 2 == 1) res = (res * base) % mod;
        base = (base * base) % mod;
        exp /= 2;
    }
    return res;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int T;
    cin >> T;
    while (T--) {
        long long a, b;
        cin >> a >> b;
        long long b_inv = power(b, p - 2, p);
        long long ans = (a % p + p) % p;
        ans = (ans * b_inv) % p;
        cout << ans << endl;
    }
    return 0;
}

import java.util.Scanner;

public class Main {
    static final int p = 1000000007;

    public static long power(long base, long exp, long mod) {
        long res = 1 % mod;
        base %= mod;
        while (exp > 0) {
            if (exp % 2 == 1) {
                res = (res * base) % mod;
            }
            base = (base * base) % mod;
            exp /= 2;
        }
        return res;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int T = sc.nextInt();
        while (T-- > 0) {
            long a = sc.nextLong();
            long b = sc.nextLong();
            long b_inv = power(b, p - 2, p);
            long ans = (a % p + p) % p;
            ans = (ans * b_inv) % p;
            System.out.println(ans);
        }
    }
}

P = 1000000007

T = int(input())
for _ in range(T):
    a, b = map(int, input().split())
    # 使用内置的 pow(base, exp, mod) 计算 b 的逆元 b^(P-2)
    b_inv = pow(b, P - 2, P)
    ans = (a * b_inv) % P
    print(ans)

算法及复杂度

算法：费马小定理 + 快速幂
时间复杂度： $\mathcal{O}(T \cdot \log p)$ ，对于每个测试用例，都需要调用一次快速幂来计算逆元。
空间复杂度： $\mathcal{O}(1)$ 。