#NOIP2017J1Q31. [NOIP 2017 普及组初赛] 第 31 题
[NOIP 2017 普及组初赛] 第 31 题
(快速幂) 请完善下面的程序,该程序使用分治法求x p mod m 的值。 输入: 三个不超过10000 的正整数x,p,m。 输出: x p mod m 的值。 提示: 若p为偶数,x p =(x 2 ) p/2 ;
若p为奇数,x p =x*(x 2 ) (p-1)/2 。
#include <iostream>
using namespace std;
int x, p, m, i, result;
int main() {
cin >> x >> p >> m;
result = 【第1空】;
while ( 【第2空】) {
if (p % 2 == 1)
result = 【第3空】;
p /= 2;
x = 【第4空】;
}
cout << 【第5空】 << endl;
return 0;
}
请填写【第4空】。
{{ input(1) }}