「一本通 6.1 练习 1」A 的 B 次方

题目描述

给定正整数 $a,b,m$ （ $1\le a,b,m\le 10^9$ ），求 $a^b\bmod m$ 。

输入一行三个整数 $a,b,m$ ；输出一个整数表示结果。

样例输入：2 100 1007，样例输出：169。

思路

把指数 $b$ 拆成二进制，边平方边取模：若 $b$ 的当前最低位为 $1$ 就把底数乘入答案，然后底数自乘、 $b$ 右移一位。时间 $O(\log b)$ 。

参考代码

Python 版：

python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20#!/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-09-30 22:18
# update_at: 2026-09-30 22:18

import sys


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

    # a^b 完整展开有 b*log10(a) 位（b 可达 1e9），先算幂再取模会撑爆内存，
    # 必须边平方边取模；三参数 pow 底层正是二进制快速幂，指数每折半一次。
    print(pow(a, b, m))


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
33
34/**
 * 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 01:04
 * update_at: 2026-10-06 01:04
 */

#include <iostream>
using namespace std;

typedef long long ll;

ll a, b, m;

// 二进制快速幂：把指数 b 拆成二进制，边平方边取模
ll qpow(ll base, ll exp, ll mod) {
    ll ans = 1 % mod;
    base %= mod;
    while (exp > 0) {
        if (exp & 1) ans = ans * base % mod; // 当前二进制位为 1，乘入答案
        base = base * base % mod;            // 底数平方，准备下一位
        exp >>= 1;
    }
    return ans;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> a >> b >> m;
    cout << qpow(a, b, m) << '\n';
    return 0;
}

「一本通 6.1 练习 1」A 的 B 次方

目录

题目描述

思路

参考代码