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

题目

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

题解

考点定位

本题（快速幂第②空）考「循环/递归条件」,对应大纲 4.3.1 快速幂（难度【2】）。

解题过程

②处继续条件：

``cpp while (p > 0) ``

答案：p > 0。

易错提醒

① 迭代版快速幂：p 二进制从低位到高位；② p==0 结束。