龟速乘算法

AcWing 90. 64位整数乘法

题目

https://www.acwing.com/problem/content/92/ 求 a 乘 b 对 p 取模的值。 $1≤a,b,p≤10^{18}$

思路

如果直接计算a乘b会超过long long 的最大范围，这里采用类似快速幂的思想 将b写成二进制形式：$b=2^{x1}+2^{x2}+...+2^{xi}$ 所以$a × b mod p=(a× 2^{x1} mod p)+(a × 2^{x2} mod p)+...$

代码

#include <bits/stdc++.h>

using namespace std;

typedef long long LL;
LL a, b, p;

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

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