(快速幂)请完善下面的程序,该程序使用分治法求 xp
(快速幂)请完善下面的程序,该程序使用分治法求 xp mod m 的值。
输入:三个不超过 10000 的正整数 x, p, m。
输出:xp mod m 的值。
提示:若 p 为偶数,xp = (x2)p/2;若 p 为奇数,xp = x (x2)(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 ;
}答案
第1空:1
第2空:p > 0
第3空:result * x % m
第4空:x * x % m
第5空:result