01二分快速冪-創(chuàng)新互聯(lián)

1、模冪運(yùn)算

創(chuàng)新互聯(lián)建站服務(wù)項(xiàng)目包括東陽(yáng)網(wǎng)站建設(shè)、東陽(yáng)網(wǎng)站制作、東陽(yáng)網(wǎng)頁(yè)制作以及東陽(yáng)網(wǎng)絡(luò)營(yíng)銷策劃等。多年來(lái)，我們專注于互聯(lián)網(wǎng)行業(yè)，利用自身積累的技術(shù)優(yōu)勢(shì)、行業(yè)經(jīng)驗(yàn)、深度合作伙伴關(guān)系等，向廣大中小型企業(yè)、政府機(jī)構(gòu)等提供互聯(lián)網(wǎng)行業(yè)的解決方案，東陽(yáng)網(wǎng)站推廣取得了明顯的社會(huì)效益與經(jīng)濟(jì)效益。目前，我們服務(wù)的客戶以成都為中心已經(jīng)輻射到東陽(yáng)省份的部分城市，未來(lái)相信會(huì)繼續(xù)擴(kuò)大服務(wù)區(qū)域并繼續(xù)獲得客戶的支持與信任！

這里求??的??次冪(次方)對(duì)??取余數(shù)的計(jì)算，被稱為模冪運(yùn)算，本文會(huì)針對(duì)以上的式子，根據(jù)數(shù)據(jù)范圍提供完全不同的算法來(lái)進(jìn)行講解，確保正確性的前提下，以求達(dá)到時(shí)間和空間的平衡；
高端的算法往往只需要采用最樸素的詮釋方式。

樸素算法

1）枚舉

直接一個(gè)??次的循環(huán)，枚舉對(duì)??的??次乘法：

最后進(jìn)行取模運(yùn)算（c++中的 '%' 符號(hào)等價(jià)于數(shù)學(xué)中的取模 mod）；
c++代碼實(shí)現(xiàn)如下：

int f(int a, int b, int c) {
    int ans = 1;
    while(b--)
        ans = ans * a;
    return ans % c;
}

這段代碼有沒(méi)有問(wèn)題呢？

溢出問(wèn)題：首先，在數(shù)據(jù)量比較大的時(shí)候，運(yùn)算結(jié)果會(huì)出現(xiàn)負(fù)數(shù)，這是因?yàn)閕nt 的取值范圍是 [-2^31,2^31]，超過(guò)后就會(huì)溢出，結(jié)果就和預(yù)期的不符了；

時(shí)間復(fù)雜度：其次，這個(gè)算法的時(shí)間復(fù)雜度是O(b)的，當(dāng)b很大的時(shí)候，明顯是無(wú)法滿足時(shí)間要求的，尤其是寫(xiě)服務(wù)器代碼的時(shí)候，時(shí)間復(fù)雜度尤為重要，10個(gè)、100個(gè)、1000 個(gè)玩家出現(xiàn)這樣的計(jì)算時(shí)，時(shí)間消耗都是成倍增長(zhǎng)的，非常占用服務(wù)器 CPU 資源；

那么，我們先保證正確性，確保計(jì)算過(guò)程中不會(huì)溢出，這里就需要用到數(shù)論里面一些簡(jiǎn)單的知識(shí)：模乘。

2）模乘

模乘滿足如下公式：

證明如下：

所以我們可以對(duì)樸素算法進(jìn)行一些改進(jìn)，改進(jìn)如下：

int f(int a, int b, int c) {
    int ans = 1 % c;
    while(b--)
        ans = ans * a % c;
    return ans;
}

利用模乘運(yùn)算，可以先模再乘，每次運(yùn)算完畢確保數(shù)字是小于模數(shù)的，這樣確保數(shù)字不會(huì)太大而造成溢出，但是這里沒(méi)有考慮一種情況，就是??有可能是負(fù)數(shù)；

3）負(fù)數(shù)考慮

需要再進(jìn)行一次改進(jìn)，改進(jìn)版如下：

int f(int a, int b, int c) {
    a = (a % c + c) % c;
    int ans = 1 % c;
    while(b--)
        ans = ans * a % c;
    return ans;
}

我們發(fā)現(xiàn)只需要多加一句話：

a%c 是為了確保模完以后a的絕對(duì)值小于c，如圖上圖所示；?

再加上c是為了保證結(jié)果是正數(shù)，如上圖所示；

最后又模上c是為了確保a是正數(shù)的情況也能準(zhǔn)確讓結(jié)果落在(0,c)的范圍內(nèi)，如上圖所示；

這樣改完還有哪些問(wèn)題呢？？？

1、溢出問(wèn)題：溢出問(wèn)題仍然存在，只要c的范圍是 [-2^31,2^31],ans和a的范圍就在(0,c) ，ans*a的范圍就是(0,c^2) ，最壞情況就是(0,2^62) ，還是超過(guò)了int的范圍；

2、時(shí)間復(fù)雜度：時(shí)間復(fù)雜度仍然是O（b）的，而且每次都有一個(gè)取模運(yùn)算，常數(shù)時(shí)間變大了；

為了改善溢出問(wèn)題，我們可以在相乘的時(shí)候轉(zhuǎn)成long long來(lái)避免，c++ 代碼實(shí)現(xiàn)如下：

int f(int a, int b, int c) {
    a = (a % c + c) % c;
    int ans = 1 % c;
    while(b--)
        ans = (long long)ans * a % c;
    return ans;
}

溢出問(wèn)題暫且告一段落，接下來(lái)讓我們考慮下如何改善時(shí)間復(fù)雜度的問(wèn)題（也許有人會(huì)問(wèn)，如果c模數(shù)的范圍是long long,? ?又該怎么辦呢？）；

2、循環(huán)節(jié)

1）?小數(shù)據(jù)分析

2）算法實(shí)現(xiàn)

算法時(shí)間復(fù)雜度為O(K) ；

基于K的不確定性，并且時(shí)間復(fù)雜度應(yīng)該是算最壞情況下的，所以這個(gè)算法的實(shí)際時(shí)間復(fù)雜度是O(c)；

c++代碼實(shí)現(xiàn)如下：

#define MAXN 100005
int F[MAXN+1], FPos[MAXN+1];
int f(int a, int b, int c) {
    memset(FPos, -1, sizeof(FPos));
    F[0] = 1 % c;
    FPos[ F[0] ] = 0;
    for(int i = 1; i<= b; ++i) {
        F[i] = F[i-1] * a % c;
        int &pre =  FPos[ F[i] ];
        if( pre == -1) {
            pre = i;
        }else {
            int K = i - pre;
            int Index = ( b - pre ) % K + pre;
            return F[Index];
        }
    }
    return F[b];
}

2、二分快速冪

1) 遞歸實(shí)現(xiàn)

#define ll long long
ll f(ll a, ll b, ll c) {
    if (b == 0)
        return 1 % c;
    ll v = f(a*a % c, (b>>1), c);
    if (b & 1)
        v = v * a % c;
    return v;
}

代碼實(shí)現(xiàn)非常簡(jiǎn)單，根據(jù) c++ 整數(shù)除法是取下整的特性，偶數(shù)和奇數(shù)的除法可以統(tǒng)一處理，然后用位運(yùn)算進(jìn)行一部分優(yōu)化；
1）右移一位相當(dāng)于除2；
2）位與(&) 1 用于判斷奇偶性；

2) 二進(jìn)制優(yōu)化實(shí)現(xiàn)

c++ 代碼實(shí)現(xiàn)如下

#define ll long long
ll f(ll a, ll b, ll c){
    ll ans = 1;
    while(b) {
        if(b & 1) ans = ans * a % c;     // 1）
        a = a * a % c;                   // 2）
        b >>= 1;                         // 3）
    }
    return ans;
}

1）和 3）是配合著做的，檢查n的第i位二進(jìn)制低位否是1，如果是則乘上對(duì)應(yīng)的a次冪：a^(ni)其中ni=2^i;
2）依次求出a1 a2 a4 a8........；
這個(gè)算法的時(shí)間復(fù)雜度為O(logb)，相比遞歸算法減少了一些常數(shù)消耗；

3、模數(shù)為 64 位整數(shù)

c++ 代碼實(shí)現(xiàn)如下

#define ll long long
ll Product_Mod(ll a, ll b, ll c) {
    ll sum = 0;
    while(b) {
        if(b & 1) sum = (sum + a) % c;
        a = (a + a) % c;
        b >>= 1;
    }
    return sum;
}
ll f(ll a, ll b, ll c) {
    ll ans = 1;
    while(b) {
        if(b & 1) sum = Product_Mod(sum, a, c);
        a = Product_Mod(a, a, c);
        b >>= 1;
    }
    return ans;
}

4、時(shí)間復(fù)雜度總結(jié)

你是否還在尋找穩(wěn)定的海外服務(wù)器提供商？創(chuàng)新互聯(lián)www.cdcxhl.cn海外機(jī)房具備T級(jí)流量清洗系統(tǒng)配攻擊溯源，準(zhǔn)確流量調(diào)度確保服務(wù)器高可用性，企業(yè)級(jí)服務(wù)器適合批量采購(gòu)，新人活動(dòng)首月15元起，快前往官網(wǎng)查看詳情吧

網(wǎng)站標(biāo)題：01二分快速冪-創(chuàng)新互聯(lián)
網(wǎng)站網(wǎng)址：http://muchs.cn/article20/ceegco.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供面包屑導(dǎo)航、定制開(kāi)發(fā)、ChatGPT、網(wǎng)站制作、電子商務(wù)、外貿(mào)網(wǎng)站建設(shè)

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請(qǐng)盡快告知，我們將會(huì)在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng)，如需處理請(qǐng)聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時(shí)需注明來(lái)源：創(chuàng)新互聯(lián)

猜你還喜歡下面的內(nèi)容