P1226 【模板】快速幂

题目描述

给你三个整数 $a,b,p$，求 $a^b \bmod p$。

输入格式

输入只有一行三个整数，分别代表 $a,b,p$。

输出格式

输出一行一个字符串 a^b mod p=s，其中 $a,b,p$ 分别为题目给定的值， $s$ 为运算结果。

输入输出样例 #1

输入 #1

2 10 9

输出 #1

2^10 mod 9=7

说明/提示

样例解释

$2^{10} = 1024$，$1024 \bmod 9 = 7$。

数据规模与约定

对于 $100\%$ 的数据，保证 $0\le a,b < 2^{31}$，$a+b>0$，$2 \leq p \lt 2^{31}$。

思路分析 + 代码实现

对于指数 exp ，我们通过 右移（>>） 运算符，遍历其在二进制表示下的每一位，用 按位与（&） 运算符取出 exp 在二进制表示下的最低位。在循环到第 i 次时，变量 base 中存储的是 $base^{2^i}$ ，若 exp 该位为 1 ，则把此时的变量 base 累乘到 result 中。代码如下：

#include<bits/stdc++.h>
using namespace std;
// 计算 base 的 exponent 次方，结果对 mod 取模
long long power(long long base, long long exp, const long long mod) {
    if (exp == 0) return 1;
    long long result = 1;
    while (exp) { // 每次处理 exp 的二进制最低位，然后右移 1 位
        if (exp & 1) // 若 exp 的二进制最低位为 1
            result = result * base % mod; // 相当于将这一位二进制位变为 1
        base = base * base % mod; // base 平方，相当于指数左移 1 位
        exp >>= 1; // 处理下一个二进制位
    }
    return result;
}
int main() {
    long long a, b, p;
    cin >> a >> b >> p;
    cout << a << "^" << b << " mod " << p << "=" << power(a,b,p);
    return 0;
}