文章

11

粉丝

414

获赞

8

访问

100.0k

头像
快速幂
P1017 贵州大学机试题
发布于2020年6月24日 20:02
阅读数 12.5k

  本题对于没有接触过快速幂算法的人来说应该是有很大难度,因为题目要求时间复杂度O(logn),不能使用暴力循环。

要解决本题必须要了解求幂取模运算的法则,比如本题涉及的 (a*b) % p = (a%p * b%p) %p;这是解决本题的核心。下边先上代码:

#include <iostream> 
using namespace std;
#define LL long long 

//位运算快速幂
 LL fastPower(LL base, LL power, int p)//p为对谁求余 
 {
	LL res = 1;
	while(power > 0)
	{
		if(power & 1) //奇数和1与运算结果为 1 相当于power%2 == 1 
			res = res * base % p;
		power >>= 1;//power 的二进制向右移动一位相当于power /= 2 
		base = base * base % p;
	}
	return res;
}
int main()
{
	 int x, n;
	 cin >> x >> n; 
	 int p = 233333;
	 LL res = fastPower(x,n,p);
	 cout << res;
	return 0;	
}

简单介绍下大致原理:比如求解 3^10,要使指数缩小就得使底数变大,此时指数为偶数,3^10 = (3*3)^5 即 9^5,此时底数变为 base = base * base, 接下来指数为5此时为奇数,9^5 = 9^4 * 9^1(9^1已经存入res,此时5为奇数)本来要对指数减一才可以得到9^4 ,但是计算机中除法操作默认向下取整,故此时 power = 5; 仍然执行 power=  power / 2操作,即有 9^5 = 81^2 *9^1,然后又有 9^5 = ( 6561 )^1 * 9^1 此时power又为奇数,同理可得9^5 =( 6561 )^0 * 6561^1 * 9^1,(6561^1已经存入res,此时1为奇数 )此时powe...

登录查看完整内容


登录后发布评论

暂无评论,来抢沙发