题目描述

求 $a$ 乘 $b$ 对 $p$ 取模的值，其中 $1 \le a,b,p \le 10^{18}$。

样例

输入：

3
4
5

输出：

2

算法

(位运算) $O(\log_2 b)$

把整数 $b$ 用二进制表示，即 $b=c_{k-1}2^{k-1}+c_{k-2}2^{k-2}+ \dots +c_02^0$，那么 $a \ast b=c_{k-1} \ast a \ast 2^{k-1}+c_{k-2} \ast a \ast 2^{k-2}+ \dots +c_0 \ast a \ast 2^0$。
因为 $a \ast 2^i=(a \ast 2^{i-1}) \ast 2$，若已求出 $a \ast 2^{i-1} \bmod p$，则计算 $(a \ast 2^{i-1}) \ast 2 \bmod p$ 时，运算过程中每一步的结果都不超过 $2 \ast 10^{18}$，仍然在 $64$ 位整数 $\operatorname{long long}$ 的表示范围内，所以很容易通过 $k$ 次递推求出每个乘积项。当 $c_i=1$ 时，把该乘积项累加到答案中即可。

时间复杂度

$O(\log_2 b)$

C++ 代码

#include <bits/stdc++.h>

using namespace std;

long long a, b, p, ans;

long long mul(long long a, long long b, long long p)
{
    for (; b; b >>= 1)
    {
        if (b & 1)
            ans = (ans + a) % p;
        a = a * 2 % p;
    }
    return ans;
}

int main()
{
    cin >> a >> b >> p;
    cout << mul(a, b, p) << '\n';
    return 0;
}