如何高效计算快速幂模运算 a^b % p？

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

题目描述：求$a^b \mod p$的值。

输入格式：三个整数$a, b, p$，用逗号隔开。

输出格式：输出一个整数，表示$a^b \mod p$的值。

数据范围：$0 \leq a, b \leq 10^9$，$2 \leq p \leq 10^{10}$。

示例：输入：2, 3, 5输出：3

题目描述

求 $a$ 的 $b$ 次方对 $p$ 取模的值。 输入格式 三个整数 $a,b,p$ ,在同一行用空格隔开。 输出格式 输出一个整数，表示​​a^b mod p​​的值。 数据范围

$​0≤a,b≤10^9$ $​1≤p≤10^9$ 输入样例：

3 2 7

输出样例：

2

思路

对于C++，直接求 $a ^ b % p$ 会超过存储最大值，所以可以用反复平方法/快速幂方式计算。 $a^b$ 将 $b$ 表示成二进制，不妨设 $b=11010$

我们先预处理求出： $a^{2^0} = a$ $a^{2^1} = ({a^{2^0}})^2$ $以此类推...$

之后我们可以将 $a^b$ 拆分成 $a^{2^0} * a^{2^1} * a^{2^3} * a^{2^4}$, 其中每个值我们都可以从预处理中获取

代码

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