二分快速幂
标签: 机试攻略 - 高分篇
学习人数: 18.7k


高清播放
赞赏支持

有一类题目是这样的

求 (x^y) % p

当y很大的时候,我们不能直接用for去一个一个的乘,因为这样的方法复杂度是O(N)的。那么有没有更高效的方法呢?

遇到这类问题的时候,我们就可以使用二分快速幂的方法来求解。
举个例子

3^7 = 3^4 * 3^2 *3^1

首先我们要知道,对于任意一个数s,它的二进制代表了它可以由2的次幂的累加和来表示。
比如7的二进制是111
那么它就是说 7 = 2^2 + 2^1 + 2^0
再比如一个数12的二进制是1101

13 = 2^3 + 2^2 + 2^0

所以对于任意一个x^y,我们都可以将y分解成2的幂次的形式。
例如5^13 = 5^8 * 5^4 * 5^1

这样做有什么好处呢?

1..2..4..8..16..32..64..128........1024.....

你发现其中的奥秘了吗?

1、每一个数都是它前一个数的2倍
2、它的迭代速度超级快


 

幂次方
题目描述:
对任意正整数N,求X^N%233333的值。
要求运算的时间复杂度为O(logN)。
例如
X30 = X15*X15
X15=X7*X7*X
X7=X3*X3*X
X3=X*X*X
共7次乘法运算完毕。
输入描述:
输入两个整数X和N,用空格隔开,其中X,N<=10^9。
输出描述:
输出X^N对233333取模的结果。
输入样例#:
2 5
输出样例#:
32
题目来源:
DreamJudge 1017


题目解析:运用上面讲过的二分快速幂思想和同余模定理即可。

 

参考代码

#include <bits/stdc++.h>  
using namespace std;  
  
typedef long long ll;  
ll mod_pow(ll x, ll y, ll mod) {  
    ll res = 1;  
    while (y > 0) {  
        //如果二进制最低位为1、则乘上x^(2^i)  
        if (y & 1) res = res * x % mod;  
        x = x * x % mod;  // 将x平方  
        y >>= 1;  
    }  
    return res;  
}  
  
int main() {  
    ll x, n;//注意x*x会超出int范围  
    scanf("%lld%lld", &x, &n);  
    printf("%lld\n", mod_pow(x, n, 233333));  
    return 0;  
}  

 

登录查看完整内容


课后作业

掌握二分快速幂


登录后开始许愿

暂无评论,来抢沙发