题解：P10446 64位整数乘法

CSP_SAKME · 2024-05-15 18:58:34 · 题解

我们使用了一个循环来计算 a \times b 的结果，并在每次循环中更新结果。在每次循环中，我们将 a 乘以 2，并将结果对 p 取模。如果 b 的最低位为 1，我们将当前的结果加上 a，并对 p 取模。最后，我们返回计算得到的结果。

#include<bits/stdc++.h>
using namespace std;
long long mod(long long a, long long b, long long p) {//不开long long见祖宗！
    long long result = 0;
    a%=p;
    while(b>0) {
        if(b&1) {
            result = (result + a) % p;
        }
        a=(a<<1)%p;
        b>>=1;
    }
    return result;
}
int main() {
    long long a, b, p;
    cin >> a >> b >> p;
    cout << mod(a, b, p) << endl;
    return 0;
}