菜鸟初尝快速幂

一、快速幂原理

\[ 快速幂算法,可以加快运算速度,使用快速幂算法时间复杂度为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;
}

关键词:long 快速 使用 ll ans gt 运算 amp 一位 进制

相关推荐:

整数快速幂(取模)、矩阵快速幂及其应用

ACM数论-快速幂

快速幂取模

【模板】矩阵快速幂

浅谈快速幂

蟠桃记《快速幂》(两种解法)

快速幂&&矩阵快速幂

又见斐波那契~矩阵快速幂入门题

快速幂取模