如何高效计算快速幂模运算 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$ 会超过存储最大值，所以可以用反复平方法/快速幂方式计算。