设为首页 加入收藏

TOP

菜鸟初尝快速幂
2018-12-05 10:12:05 】 浏览:126
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(217) }