CH0102 64 位整数乘法

Description

求 a 乘 b 对 p 取模的值，其中。

Input

第一行 a，第二行 b，第三行 p。

Output

一个整数，表示的值。

Sample Input

1
2
3

2
3
9

Sample Output

Limit

Time Limit	Memory Limit
C/C++/Rust/Pascal 1 秒，其他语言 2 秒	C/C++/Rust/Pascal 32 M，其他语言 64 M

Analysis

由于，很明显不能直接乘（会爆 long long）。
回到对乘法的理解：

显然我们可以通过多步加法来实现乘法。但是，意味着朴素的累加注定会 TLE。如何优化呢？有个同类问题「快速幂」见POJ1995 Raising Modulo Numbers，根据对快速幂的理解很容易设计出 “ 慢速乘 “：

Algorithm

直接计算可能超出 long long 的范围。把乘数写成二进制：

则：

因此不必把连加次，只需逐位处理。令 t 表示当前的（对取模），res 累加已经处理的位所对应的贡献：

若当前最低位是（b & 1），就把 t 加入 res。
将 t 加倍，得到下一位对应的。
将 b 右移一位，继续处理下一位。

例如时，，所以只需累加和，得到。

#include <iostream>
using LL = long long;

LL mul(LL a, LL b, LL p) {
    LL t = 1ll * a, res = 0;
    
    while(b) {
        if(b & 1) res = (res + t) % p;
        t = (t + t) % p;
        b >>= 1;
    }

    return res;
}

LL a, b, p;
int main () {
    std::ios::sync_with_stdio(0);
    std::cin.tie(0);

    std::cin >> a >> b >> p;
    std::cout << mul(a, b, p);
}

算法时间复杂度为，额外空间复杂度为。

Template

template <class T>
T mul(T a, T b, T p) {
    LL t = (T)1 * a, res = 0;
    
    while(b) {
        if(b & 1) res = (res + t) % p;
        t = (t + t) % p;
        b >>= 1;
    }

    return res;
}

Ref

Nowcoder - 64位整数乘法
 Acwing - 64位整数乘法

Loading...