NOIP 普及 2017 第一轮 第 28 题：快速幂求 x^p mod m：第 1 空

题目

完善程序：
（快速幂） 请完善下面的程序，该程序使用分治法求 $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;
}

①处应填（ ）

答案

1

题解

考点定位

迭代快速幂的乘积初始化。

解题过程

①位于 result 的初始化语句，不是递归出口。

result 用于累计已处理指数部分对应的乘积。初始时尚未选入任何乘数，因此应取乘法单位元 1。之后遇到 p 的当前二进制位为 1，才把当前 x 乘入 result 并取模。

答案：1。

易错提醒

初始乘积应为 1。若设成 0，后续乘法会一直得到 0；本题使用 while 循环，没有递归调用。