<—点个赞吧QwQ

宣传一下算法提高课整理{:target=”_blank”}

求 $a$ 乘 $b$ 对 $p$ 取模的值。

输入格式

第一行输入整数$a$，第二行输入整数$b$，第三行输入整数$p$。

输出格式

输出一个整数，表示a*b mod p的值。

数据范围

$1 \\le a,b,p \\le 10^{18}$

输入样例：

3
4
5

输出样例：

2

思路

我们考虑将$b$进行二进制拆分:$b=2^{a_1}+2^{a_2}+2^{a_3}\dots$
而乘法有乘法分配律，取余也有类似的性质

所以：$a×b\bmod p=(a×2^{a_1}\bmod p)+(a×2^{a_2}\bmod p)\dots$
我们只要从小到大枚举$a×2^n$，当$b$的二进制位含有$2^n$，答案加上$a×2^n\bmod p$的值即可

代码

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