NOIP 2017 普及组初赛试题_完善程序 4.1 快速幂
1.（快速幂）请完善下面的程序，
该程序使用分治法求 xp mod m 的值。
（第一空 2 分，其余 3 分）
输入：三个不超过 10000 的正整数 x，p，m。
输出：x^p mod m 的值。
提示：
若 p 为偶数，xp=(x2)p/2；
若 p 为奇数，xp=x*(x2)(p-1)/2。
#include using namespace std;
int x, p, m, i, result;
int main()
{
cin >> x >> p >> m;
result = 1 //①;
while ( p/*②*/)
{
if (p % 2 == 1)
result = result*x*%m//③;
p /= 2;
x = x*x%m//④;
}
cout <<result/* ⑤*/ << endl;
return 0;
}
/*
1.正确答案： 1
2.正确答案： p>0 / p!=0 / p
3.正确答案： result * x % m
4.正确答案： x * x % m
5.正确答案： result
(a*b)%c=(a%c)*(b%c)%c
(x*x)%m=(x%m)*(x%m)%m
*/
