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

题目

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

⑤处应填（ ）

答案

result

题解

考点定位

本题（快速幂第⑤空）考「输出结果」,对应大纲 4.3.1 快速幂（难度【1】）。

解题过程

⑤处输出：

``cpp cout << result << endl; ``

答案：result。

易错提醒

① result 已全程取模；② 与题目要求的余数输出一致。