AcWing90. 64位整数乘法

思路类似快速幂。

令 $b = t_{k - 1} {2^{k - 1}} + t_{k - 2} 2 ^ {k - 2} + … + t_02_0$

则 $a * b = a \times t_{k - 1}{2^{k - 1}} + a \times t_{k - 2}{2^{k - 2} + … + a \times t_02_0}$

同样地，我们可以枚举每一个为 $1$ 的二进制位，然后通过以上式子进行计算。

#include <iostream>
using namespace std;
typedef long long LL;
LL a, b, p;
int main() {
    cin >> a >> b >> p;
    LL res = 0;
    while (b) {
        if (b & 1) res = (res + a) % p;
        b >>= 1;
        a = (a + a) % p;
    } 
    cout << res << endl;
    return 0;
}