首页 > 试题广场 >

(快速幂)请完善下面的程序,该程序使用分治法求 xp mod

[填空题]
(快速幂)请完善下面的程序,该程序使用分治法求 xp mod m 的值。(第一空 2 分,其余 3 分)
输入:三个不超过 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 = 1;
    while (2) {
        if (p % 2 == 1)
            result = 3;
        p /= 2;
        x = 4;
    }
    cout << 5 << endl;
    return 0;
}                                    



#include<stdio.h>
//这里我用c语言写的,求a的b次方,结果对p取余
int main()
{

	long long a;long long b;long long sum;
	long long p;
	scanf("%ld%ld",&a,&b);
	scanf("%d",&p);
	while(b>0)
	{
		if(b&1)
		sum=(sum*a)%p;
		a=(a*a)%p;
		b/=2;
	}
	printf("%d",sum%p);	
		 
	return 0;
 } 

发表于 2020-10-14 22:27:01 回复(0)