a^b

题目描述

给定整数 $a, b, p$ （ $p \neq 0$ ， $0 \leqslant a, b, p \leqslant 10^9$ ），求 $a^b \bmod p$ 的值。输入一行三个整数 $a, b, p$ ，用空格隔开；输出一个整数表示结果。样例输入 3 2 7，输出 2。约定 $0^0 = 1$ （即 $b = 0$ 时答案恒为 $1 \bmod p$ ）， $p = 1$ 时答案恒为 $0$ 。

思路

把指数 $b$ 按二进制拆成若干个 2 的幂之和，则 $a^b$ 等于 $b$ 的二进制中为 1 的那些位对应的 $a^{2^k}$ 之积。这些幂可以递推： $a^{2^{k+1}} = \left(a^{2^k}\right)^2$ ，于是每轮只需判断当前位是否为 1、把底数乘进答案，再平方底数并右移指数，共 $O(\log b)$ 次模乘。初始化 result = 1 % p、base = a % p， $b = 0$ 与 $p = 1$ 两种边界会自动得到正确结果。

参考代码

Python 版：

python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-10-01 09:05
# update_at: 2026-10-01 09:05

import sys


def mod_pow(base: int, exponent: int, mod: int) -> int:
    """快速幂：把指数拆成二进制位，逐位平方底数，只把为 1 的那些位乘进结果。"""
    result = 1 % mod  # p = 1 时任何数取模都是 0，这一行顺手处理掉该边界
    base %= mod       # a 可能大于 p，先取模能让后续乘法保持在小整数范围内
    while exponent:
        if exponent & 1:  # 最低位为 1：这一份 base^(2^k) 要乘进答案
            result = result * base % mod
        base = base * base % mod  # base^(2^k) -> base^(2^(k+1))
        exponent >>= 1            # 换到下一位
    return result


def solve() -> None:
    a, b, p = map(int, sys.stdin.buffer.read().split())
    print(mod_pow(a, b, p))


if __name__ == "__main__":
    solve()

C++ 版（同一算法）：

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-06 10:43
 * update_at: 2026-10-06 10:43
 */
#include <iostream>
using namespace std;

typedef long long ll;

// 快速幂：把指数 exponent 按二进制拆分，逐位平方底数，只把为 1 的位乘进结果
ll mod_pow(ll base, ll exponent, ll mod) {
    ll result = 1 % mod; // p = 1 时答案恒为 0，这一行一次处理掉该边界
    base %= mod;         // a 可能大于 p，先取模控制后续乘积范围
    while (exponent > 0) {
        if (exponent & 1) {
            result = result * base % mod;
        }
        base = base * base % mod; // base^(2^k) -> base^(2^(k+1))
        exponent >>= 1;
    }
    return result;
}

int main() {
    ll a, b, p;
    cin >> a >> b >> p;
    cout << mod_pow(a, b, p) << "\n";
    return 0;
}

目录

题目描述

思路

参考代码