解题思路

算法解析

  1. 核心思想：

    • 将乘法转换为加法
    • 类似二进制乘法的思路
    • 每次将 翻倍， 右移一位

  2. 关键点：

    // 初始取模，减小数值
a %= p;
b %= p;

// 使用位运算判断当前位
if(b & 1)

// 翻倍使用加法
a = (a + a) % p;

  3. 限制条件处理：

    • 所有中间值不超过
    • 只使用加法和取模运算
    • 及时取模控制数值大小

  4. 优化说明：

    • 初始取模减小数值
    • 使用位运算优化
    • 及时取模避免溢出

为什么算法正确

  1. 原理：

    • 将 看作二进制数
    • 对应位为 时累加当前的
    • 每次翻倍对应二进制位的权重

  2. 举例：

    计算 7 * 5 % 10
7 * 5 = 7 * (4 + 1)
      = 7 * 4 + 7 * 1
使用加法和取模实现

  3. 数值控制：

    • 初始取模后
    • 每次加法和翻倍后立即取模
    • 保证所有中间值不超过

代码

#include <iostream>
using namespace std;

// 计算 (a * b) % p，只使用加法和取模
int modMultiply(int a, int b, int p) {
    int res = 0;
    a %= p;
    b %= p;
    
    // 类似二进制乘法的思想
    while(b) {
        if(b & 1) {
            // 如果当前位为1，加上对应的a
            res = (res + a) % p;
        }
        // a翻倍，相当于左移一位
        a = (a + a) % p;
        // b右移一位
        b >>= 1;
    }
    return res;
}
int main() {
    int q;
    cin >> q;
    
    while(q--) {
        int a, b, p;
        cin >> a >> b >> p;
        cout << modMultiply(a, b, p) << endl;
    }
    return 0;
}

import java.util.*;

public class Main {
    static int modMultiply(int a, int b, int p) {
        int res = 0;
        a %= p;
        b %= p;
        
        while(b > 0) {
            if((b & 1) == 1) {
                res = (res + a) % p;
            }
            a = (a + a) % p;
            b >>= 1;
        }
        return res;
    }
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int q = sc.nextInt();
        
        while(q-- > 0) {
            int a = sc.nextInt();
            int b = sc.nextInt();
            int p = sc.nextInt();
            System.out.println(modMultiply(a, b, p));
        }
    }
}

def mod_multiply(a, b, p):
    res = 0
    a %= p
    b %= p
    
    while b:
        if b & 1:
            res = (res + a) % p
        a = (a + a) % p
        b >>= 1
    return res

q = int(input())
for _ in range(q):
    a, b, p = map(int, input().split())
    print(mod_multiply(a, b, p))

算法及复杂度分析

  1. 算法：快速乘

  2. 时间复杂度：

    • 每次模乘：
    • 次查询：

  3. 空间复杂度：