快速幂

思路

• 分解：

\[7^{(1010100)_2} = (7^2)^{(101010)_2} = (7^4)^{(10101)_2} = (7^8)^{(1010)_2}*7^8 \]

• 利用位运算求\(b^p\)：
  • 不断把指数向右移位，b&1取得最后一位：
  • 每次右移相当于b/2，因此移完后将底数乘二
  • 若最后一位为1，答案要额外乘上b弥补整除带来的损失
• 若要求模，可在运算过程中取模，不影响最终结果

代码实现

long long quickPow(long long b, long long p, long long mod) {
	long long ans = 1;
	while (p) {
		if (p & 1)ans = ans * b % mod;
		b = b * b % mod;
		p = p>>1;
	}
        // 注意此处取模
	return ans % mod;
}

---

P1226 【模板】快速幂||取余运算

题目描述

给你三个整数 b,p,kb,p,k，求 b^p \bmod kb**pmodk。

输入格式

输入只有一行三个整数，分别代表 b,p,kb,p,k

输出格式

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

输入输出样例

输入 #1复制

2 10 9

输出 #1复制

2^10 mod 9=7

说明/提示

样例输入输出 1 解释

2^{10} = 1024210=1024，1024 \bmod 9 = 71024mod9=7。

数据规模与约定

• 对于 100%100% 的数据，保证 0\le b,p < 2^{31}0≤b,p<231，1 \leq k \lt 2^{31}1≤k<231。

完整解答

#include <cstdio>
long long b, p, k;
long long quickPow(long long b, long long p, long long mod) {
	long long ans = 1;
	while (p) {
		if (p & 1)ans = ans * b % mod;
		b = b * b % mod;
		p = p>>1;
	}
	return ans % mod;
}
int main() {
	while (~scanf_s("%lld%lld%lld", &b, &p, &k)) {
		printf("%lld^%lld mod %lld=%lld\n", b, p, k, quickPow(b, p, k));
	}
	return 0;
}