如何高效计算快速幂模运算 a*b mod p？

本文共计340个文字，预计阅读时间需要2分钟。

题目：求模运算求 $a \times b \mod p$ 的值。输入格式：第一行：输入整数 $a$第二行：输入整数 $b$第三行：输入整数 $p$输出格式：输出一个整数，表示 $a \times b \mod p$ 的值。数据范围：$1 \leq a, b, p \leq 10^9$

题目

求 $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; }