64位整数乘法

原理

见《进阶指南》第5页。

模板题

AcWing-90-64位整数乘法

#include <iostream>
using namespace std;

typedef long long LL;

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

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