用快速幂求 b^p mod k：把 p 拆成二进制，位为 1 时乘入答案，每轮底数平方取模。
OJ: roj
题目 ID: 1326
难度:入门
标签:数学快速幂python
创建: 2026-09-30 05:19
更新: 2026-10-05 09:49
后置题目
roj 3523[NOIP2003-普及] 麦森数B 的末 500 位子问题直接复用 A 教的二进制快速幂逐步取模这一关键观察，把 b^p mod k 的模板套到 (2^P-1) mod 10^500 上，再叠加 log10 位数闭式roj 300164位整数乘法B 完整复用了 A 的二进制拆分与逐位倍增骨架：A 用底数平方升级+位为 1 才累乘求幂，B 把同一循环里的平方换成加数自加翻倍、累乘换成累加，从而在避免中间乘积溢出的同时保持 O(log b)。roj 1643「一本通 6.5 例 3」Fibonacci 前 n 项和B 的 mat_pow 直接复用 A 的迭代快速幂「底数每轮平方升级、答案按位乘入」骨架，只是把标量底数换成 2×2 转移矩阵roj 1618「一本通 6.1 练习 3」越狱B 用正难则反得到 m^n−m(m−1)^(n−1) 后，复用 A 教的把指数按二进制拆分求模幂，直接调用 pow 算出两个模幂，只是把 A 的单一幂扩成两个幂；额外台阶是补集计数与乘法原理。roj 10006涨薪B 的 main.cpp 里 ll power(ll base,ll exp)（exp&1 时 result 乘底数、底数自身平方取模、exp>>=1）正是 A 教的「二进制分解快速幂：底数逐位平方升级、位为 1 时把底数乘进答案」这一步，用来算 $3^m$、$2^m$（m 可达 1e9），B 只是在此外层叠加降序排序与「最小 k=n-x-y 人连续两年拿 C 被开除」的贪心结论与 m=1 特判。roj 12342011B 的 qpow（res=res*a%mod、a=a*a%mod、e>>=1）就是 A 教的二进制分解快速幂逐位平方、位为 1 累乘这一步，只是额外叠加指数取末四位再取模的数论化简
题目描述
输入三个长整型数 b、p、k，求 b^p mod k 的值，输出格式为 b^p mod k=结果。
思路
将 p 按二进制拆分，从低位到高位逐位处理：当前位为 1 时把底数乘进答案，每轮底数平方并对 k 取模；全程取模保证中间值不超过 k^2。
参考代码
Python 版：
python
#!/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 05:19
# update_at: 2026-09-30 05:19
import sys
def power_mod(b: int, p: int, k: int) -> int:
"""快速幂：求 b^p mod k。
p 的每一个二进制位从低位到高位依次考察：基数平方升级、位为 1 就乘进答案。
每一步都取模，保证中间值不超过 k^2，不会溢出（Python 大整数下只是让数字保持小、
乘法变快）。
"""
ans = 1
b %= k # 先把底数降到 [0, k) 再平方，防 k=1 之外还白乘大数
while p:
if p & 1: # 当前二进制位是 1：这一份底数要乘进答案
ans = ans * b % k
b = b * b % k # 底数平方升级：b^1 -> b^2 -> b^4 -> ...
p >>= 1 # 去掉已经考察过的最低位
return ans
def solve() -> None:
b, p, k = map(int, sys.stdin.buffer.read().split())
print(f"{b}^{p} mod {k}={power_mod(b, p, k)}")
if __name__ == "__main__":
solve()C++ 版（同一算法）：
cpp
/**
* 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-05 09:49
* update_at: 2026-10-05 09:49
*/
#include <iostream>
using namespace std;
typedef long long ll;
ll b, p, k;
// 快速幂：返回 b^p mod k，所有中间乘积都对 k 取模
ll qpow(ll base, ll power, ll mod) {
ll res = 1 % mod;
base %= mod;
while (power > 0) {
if (power & 1) res = (res * base) % mod;
base = (base * base) % mod;
power >>= 1;
}
return res;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> b >> p >> k;
ll ans = qpow(b, p, k);
cout << b << "^" << p << " mod " << k << "=" << ans << "\n";
return 0;
}