题目链接

【模板】分数取模

题目描述

给定 组数据，每组给出两个整数 和一个质数模数 。请你计算 的值。

解题思路

本题的核心是在模算术（Modular Arithmetic）的框架下执行除法运算。

  1. 模除法的转化

    在常规算术中，除以一个数 等价于乘以它的倒数 。在模算术中，这个概念被模乘法逆元（Modular Multiplicative Inverse）所替代。

    数 在模 意义下的乘法逆元，记作 ，是一个整数 ，满足 。

    因此，原问题 就等价于计算 。

  2. 求解模乘法逆元

    求解模逆元有多种方法，最常用的有扩展欧几里得算法和费马小定理。

    • 费马小定理：该定理有一个关键的适用条件——模数 必须是质数。题目中给定的模数 恰好是一个质数。

    费马小定理指出：如果 是一个质数，对于任意整数 且 ，有 。

    我们可以对这个同余式两边同乘以 ，得到：

    这样，我们就找到了计算 的模逆元的简单方法：计算 即可。

  3. 最终算法

    结合以上分析，我们可以得出完整的算法步骤：

    • 将原问题 转化为 。
    • 使用快速幂算法来高效地计算 的值。
    • 将 与计算出的逆元相乘，并再次对 取模，得到最终结果。
    • 注意：输入的 可能为负数。在 C++ 和 Java 等语言中，负数的 % 运算结果可能也是负数。为了确保结果始终在 区间内，需要使用 ( % + ) % 的技巧来处理。

代码

#include <iostream>

using namespace std;

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

long long mod_inverse(long long n, long long mod) {
    return fast_power(n, mod - 2, mod);
}

int main() {
    int T;
    cin >> T;
    while (T--) {
        long long a, b;
        long long p = 1000000007;
        cin >> a >> b;
        
        long long inv_b = mod_inverse(b, p);
        
        long long norm_a = (a % p + p) % p;
        
        long long result = (norm_a * inv_b) % p;
        cout << result << endl;
    }
    return 0;
}

import java.util.Scanner;

public class Main {
    public static long fastPower(long base, long power, long mod) {
        long result = 1;
        base %= mod;
        while (power > 0) {
            if (power % 2 == 1) {
                result = (result * base) % mod;
            }
            base = (base * base) % mod;
            power /= 2;
        }
        return result;
    }

    public static long modInverse(long n, long mod) {
        return fastPower(n, mod - 2, mod);
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int T = sc.nextInt();
        long p = 1000000007;
        while (T-- > 0) {
            long a = sc.nextLong();
            long b = sc.nextLong();
            
            long inv_b = modInverse(b, p);
            
            long norm_a = (a % p + p) % p;

            long result = (norm_a * inv_b) % p;
            System.out.println(result);
        }
    }
}

def fast_power(base, power, mod):
    result = 1
    base %= mod
    while power > 0:
        if power % 2 == 1:
            result = (result * base) % mod
        base = (base * base) % mod
        power //= 2
    return result

def mod_inverse(n, mod):
    return fast_power(n, mod - 2, mod)

def main():
    T = int(input())
    p = 1000000007
    for _ in range(T):
        a, b = map(int, input().split())
        
        inv_b = mod_inverse(b, p)
        
        norm_a = (a % p + p) % p
        
        result = (norm_a * inv_b) % p
        print(result)

if __name__ == "__main__":
    main()

算法及复杂度

  • 算法：数论、模乘法逆元、费马小定理、快速幂

  • 时间复杂度：。对于 组查询，每组查询的核心是计算模逆元，这需要一次快速幂运算，其时间复杂度为 。

  • 空间复杂度：。算法只使用了常数个变量来存储中间结果。