快速幂--a*b%p

题目

求 $a$ 乘 $b$ 对 $p$ 取模的值。 输入格式 第一行输入整数 $a$ ，第二行输入整数 $b$​ ，第三行输入整数 $p$ 。 输出格式 输出一个整数，表示​​a*b mod p​​的值。 数据范围 $1≤a,b,p≤10^{18}$ 输入样例：

3
4
5

输出样例：

2

思路

$a * b % p$ 等价于 $b$ 个 $a$ 相加 $% p$ 不妨设$b = 10011$ 先预处理: $a = ..$ $2a = ..$ $4a = ..$ $8a = ..$ ...

由上可以得到 $a * b = a2^0 + a2^1 + a* 2^4$ 相比于快速幂求 $a^b % p$, 区别是将 $*$ 改成 $+$

代码

#include <iostream>

using namespace std;

typedef long long LL;

LL fast_power(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()
{
    LL a, b, p;
    cin >> a >> b >> p;
    
    cout << fast_power(a, b, p) << endl;
    
    return 0;
}