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