快速幂(取模)算法

2019-04-13 13:03发布

站内文章 / 模拟电子
10453 0 1799
对于普通类型的求a^n，我们的求法是不是a*a*a*a....，这样乘以n次，时间复杂度为O(n)，对于普通n比较小的我们可以接受，然而当n比较大的时候，计算就慢了，所以我们就去寻找更快捷的计算方法！例如：我们要求2^8，我们通过当为偶数的时候，a^n=(a*a)^(n/2)，当n为奇数时，a^n=a*(a*a)^(n/2)的形式，是不是可以转化为4^4->8^2->64^1，就可以了，2^5的话2*4^2->2*16^1。下面直接给出代码吧。int power(int a, int n) { int ans = 1; while(n > 0) { if(n&1) //当n为奇数时，乘以余下的一个a ans *= a; a *= a; n /= 2; } return ans; }但是当n比较大时往往我们的结果都非常大，如果直接算的话就会溢出，所以我们在计算的过程中会对结果取模，然后我们就有了快速幂取模算法。控制数据的大小，对于取模我们有(a*b)%c = ((a%c)*(b%c))%c，给出代码。
int power(long long a, int n) { long long ans = 1; while(n > 0) { if(n&1) { ans *= a; ans %= mod; } a *= a%mod; a %= mod; n /= 2; } return ans%mod; }

热门文章