64位整数乘法

题目描述

求 $a$ 乘 $b$ 对 $p$ 取模的值。输入共三行，每行一个整数，依次为 $a$ 、 $b$ 、 $p$ ；输出一个整数，表示 $a \times b \bmod p$ 的值。

数据范围： $1 \le a, b, p \le 10^{18}$ 。输入样例为 3、4、5（各占一行），输出样例为 2。

思路

$a \times b$ 最大约 $10^{36}$ 会溢出 long long，所以把乘数 $b$ 按二进制拆成若干 $2$ 的幂之和： $b$ 的最低位为 1 时把当前加数 $a \cdot 2^k \bmod p$ 累进答案，然后加数自加翻倍、 $b$ 右移一位。答案与加数始终保持在 $[0, p)$ ，每次加法后取模的中间量不超过 $2p$ ，不会溢出，总时间 $O(\log b)$ 。

参考代码

Python 版：

python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-10-01 09:43
# update_at: 2026-10-01 09:43

import sys


def mod_mul(a: int, b: int, mod: int) -> int:
    """龟速乘：把 b 按二进制拆成若干 2 的幂之和，用逐位翻倍的加法代替乘法。"""
    result = 0
    a %= mod            # a 可能不小于 p，先取模把加数压回 [0, p)，后续加法才不越界
    while b:
        if b & 1:                       # 最低位为 1：这一份 a*2^k 要加进答案
            result = (result + a) % mod
        a = (a + a) % mod               # a*2^k -> a*2^(k+1)，翻倍加法代替乘 2
        b >>= 1                         # 换到下一位
    return result


def solve() -> None:
    a, b, p = map(int, sys.stdin.buffer.read().split())
    print(mod_mul(a, b, p))


if __name__ == "__main__":
    solve()

C++ 版（同一算法）：

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-06 10:53
 * update_at: 2026-10-06 10:53
 */

#include <cstdio>

typedef long long ll;

// a, b, p 最大 1e18，a*b 会超 long long，只能用龟速乘
ll a, b, p;

// 龟速乘：把 b 按二进制拆成若干 2 的幂之和，用逐位翻倍的加法代替乘法
// 核心是 (x + y) % p = ((x%p) + (y%p)) % p，result 和 a 始终保持 < p，和不超过 2p，不会溢出
ll mod_mul(ll a, ll b, ll p) {
    ll result = 0;      // 已收编二进制位的和，初值 0（加法单位元）
    a %= p;             // a 可能不小于 p，先压回 [0, p)，后面加法才不越界
    while (b) {
        if (b & 1)                  // b 的最低位为 1：这份 a*2^k 加进答案
            result = (result + a) % p;
        a = (a + a) % p;            // a*2^k 翻倍成 a*2^(k+1)，加法代替乘 2
        b >>= 1;                    // 消费下一位
    }
    return result;
}

int main() {
    scanf("%lld%lld%lld", &a, &b, &p);
    printf("%lld\n", mod_mul(a, b, p));
    return 0;
}

目录

题目描述

思路

参考代码