题目链接

算法竞赛进阶指南-2.64位整数乘法

Method : 位运算-二进制拆分

基础位运算，类似于快速幂，用了倍增的思想:

${a * 1 = a}$;

${a * 2 = 2a}$;

${a * 4 = 4a}$;

${a * 8 = 8a}$;
…

对于任意一个b，都可以把b拆成一个2进制数表达

如：${9 = (1001)_2 = 1 * 8 + 0 * 4 + 0 * 2 + 1 * 1}$

注意两点:

1. 有取模运算时不要用自加+=， 否则会影响计算顺序
2. return 时也要取模， 防止极端例子:b = 0且p = 1

#include <iostream>
#include <algorithm>

using namespace std;

typedef unsigned long long LL;

LL a, b, p;

LL int64_mul(LL a, LL b) {
    LL res = 0LL;
    while (b) {
        if (b & 1) {
            res = (res + a) % p;
        }
        a = (a + a) % p;
        b = b >> 1;
    }
    return res % p;
}

int main() {
    cin >> a >> b >> p;
    cout << int64_mul(a, b) << endl;
    return 0;
}

复杂度分析

• 时间复杂度${O(log_2b)}$， 其中$log_2b$为对$b$进行二进制拆分的时间复杂度。

• 空间复杂度${O(1)}$。