NOIP 普及组初赛 · NOIP 2017 普及组初赛试题 第 27 题

完善程序： （快速幂） 请完善下面的程序，该程序使用分治法求 $x^{p} \bmod\ m$ 的值。（第一空 $2$ 分，其余 $3$ 分）

输入：三个不超过 $10000$ 的正整数 $x,p,m$。 输出：$x^{p} \bmod\ m$的值。 提示：若 $p$ 为偶数，$x^{p}=(x^{2})^{p/2}$；若 $p$ 为奇数，$x^{p}=x\times (x^{2})^{(p-1)/2}$。

#include<iostream>
using namespace std;
int x, p, m, i, result;
int main(){
	cin >> x >> p >> m;
	result = ①;
	while (②){
		if (p % 2 == 1)
			result = ③;
		p /= 2;
		x = ④;
	}
	cout << ⑤ << endl;
	return 0;
}

快速幂：p 为奇数乘 x，p 折半 x 平方，循环至 p=0。

①result 初值必为 1；③④每步必须取模防溢出；⑤输出 result 而非 x。

考点：快速幂算法｜循环控制｜取模运算

程序在做什么

输入 x,p,m，通过二进制分解指数 p，迭代计算 x^p mod m。