菜鳥初嘗快速冪

一、快速冪原理

\[ 快速冪算法,可以加快運算速度,使用快速冪算法時間複雜度為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 快速 使用 ans 運算 ll 二進制 最後 可以 的話

相關推薦:

解析·優化 ZKW線段樹

CCF-NOIP-2018 提高組(複賽) 模擬試題(四)

[CEOI2015 Day2]世界冰球錦標賽 (折半搜索)

test20180907 day1

第一次代碼作業

[2018湖南省隊集訓] 6.28 T2 color

因子和

B

看無可看