设为首页 加入收藏

TOP

菜鸟初尝快速幂
2018-12-05 10:12:05 】 浏览:17
Tags:菜鸟 快速

一、快速幂原理

\[ 快速幂算法,可以加快运算速度,使用快速幂算法时间复杂度为O(logN) \]

\[ 以2^{50}为例 \]

? 在不使用数学函数的情况下,使用遍历的方法,时间复杂度是O(N),需要遍历50次对吧。

? 但是如果使用快速幂的话,那就快多了。具体是如何运算,先将50转化成2进制数 110010,那么50就可以转化为
\[ 2^5+2^4+2^1 \]
? 这是如何实现的呢?我们使用二进制很轻松就可以做到这样了。
\[ 110010 = 1*2^5 + 1*2^4 + 0*2^3 + 0*2^2 + 1*2^1 + 0*2^0 \]

\[ 2^{50} = 2^{2^5} * 2^{2^4} *2^{2^1} \]

? 很显然这样运算的话比遍历快的多得多了。

二、代码实现

非常简洁b&1的意思是判断二进制最后一位为不为1,也可以使用 b%2代替;b>>1的意思是二进制右移一位(通俗的讲就是去掉二进制最后一位),也可使用b/2代替。关于位运算,以后再补充。

long long ksm(long long a, long long b)
{
    long long ans;
    
    while(b)
    {
        if(b&1)
            ans *= a;
        a *= a;
        b = b>>1;
    }
    return ans;
}

这就是快速幂的一个模板了,很简单,易记。

三、实战

? 来吧,来搞12.2的C题吧。

Stat Origin Title Problem Title
Solved C HDU 1097 A hard puzzle

题中给的数据范围很大,如果直接暴力的话,那肯定就爆炸了,long long也装不下,所以此时非常适合使用快速幂配合运算过程中的同余取模,这样既取了最后一位,还减小了数,运算速度也极快。

#include<stdio.h>
typedef long long ll;         //long long使用的
ll ksm(ll a, ll b)            //太多,简化为ll
{
    ll ans = 1;
    while(b)
    {
        if( b&1)
            ans = (ans*a)%10; //对每次运算都模10
        a = a*a%10;           //取最后一位
        b = b >> 1;
    }
    return ans;
}

int main()
{
    ll a, b;
    while(~scanf("%lld%lld", &a, &b))
    {
        printf("%lld\n", ksm(a,b));
    }
    return 0;
}

编程开发网
】【打印繁体】【投稿】【收藏】 【推荐】【举报】【评论】 【关闭】 【返回顶部
上一篇pow函数(数学次方)在c语言的用.. 下一篇(杭电1019 最大公约数) Least C..

评论

帐  号: 密码: (新用户注册)
验 证 码:
表  情:
内  容:

array(4) { ["type"]=> int(8) ["message"]=> string(24) "Undefined variable: jobs" ["file"]=> string(32) "/mnt/wp/cppentry/do/bencandy.php" ["line"]=> int(214) }