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

题目

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

题解

考点定位

本题（快速幂第③空）考「奇数位乘底」,对应大纲 4.3.1 快速幂（难度【3】）。

解题过程

③处 p 为奇数时把当前底数乘入结果：

``cpp result = result * x % m; ``

答案：**result * x % m**。

易错提醒

① 乘完立刻取模防溢出；② 随后 x=x²、p/=2。