快速幂a^b%p怎么改写成长尾词？

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

题目描述：求表达式 \(a^b \mod p\) 的值。

输入格式：三个整数 \(a, b, p\)，用空格分隔。

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

数据范围：\(0 \leq a, b \leq 10^9\)，\(1 \leq p \leq 10^{10}\)。

示例：输入：2 3 1000000007输出：8

题目描述

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