快速幂與快速乘小結

題目連結：牛客網小白月賽12-B題

題目描述：

連結：https://ac.nowcoder.com/acm/contest/392/B

來源：牛客網

找到了心儀的小姐姐月月後，華華很高興的和她聊着天。然而月月的作業很多，不能繼續陪華華聊天了。華華為了盡快和月月繼續聊天，就提出幫她做一部分作業。

月月的其中一項作業是：給定正整數A、B、P，求 A B m o d P A^{B}modP ABmodP的值。華華覺得這實在是毫無意義，是以決定寫一個程式來做。但是華華并不會寫程式，是以這個任務就交給你了。

因為月月的作業很多，是以有T組詢問。

輸入描述:

第一行一個正整數T表示測試資料組數。

接下來T行，每行三個正整數A、B、P，含義如上文。

輸出描述:

輸出T行，每行一個非負整數表示答案。

示例1

輸入

2

2 5 10

57284938291657 827493857294857 384729583748273

輸出

2

18924650048745

快速幂:

此題同時用到了快速幂和快速乘，是以在此總結一下；

首先是快速幂是用于快速求解 A B m o d P A^{B}modP ABmodP這類問題

對于 A B m o d P A^{B}modP ABmodP 這類問題，樸素的做法是

int tmp = 1;
for(int i = 0; i < B; i++)
    tmp = (tmp * A) % MOD;
           

按照題意要求模拟 A B A^{B} AB過程中每次取餘即可；這樣做，雖然結果是對的，但是效率不夠高.時間複雜度為O(B);

那這個過程能不能加速呢？ 是可以的，就是我們今天要說的這個快速幂；

那他的原理是咋樣的呢？

如果B是偶數 那麼有 A B m o d P A^{B}modP ABmodP 等價于 A 2 B 2 m o d P A^{2^{\frac{B}{2}}}modP A22B​modP

如果B是奇數 那麼有 A B m o d P A^{B}modP ABmodP 等價于 A ∗ A 2 B − 1 2 m o d P A * A^{2^{\frac{B-1}{2}}}modP A∗A22B−1​modP

舉個例子

3 5 m o d 4 3^{5}mod4 35mod4

第一步:

初始化最終結果tmp = 1

我們發現5是奇數 是以可以将其拆分為 3 × 3 2 5 − 1 2 m o d P 3 \times 3^{2^{\frac{5-1}{2}}}modP 3×3225−1​modP

顯然 我們可以計算出

tmp = tmp × \times × A, A = A × \times × A

然後對B進行右移操作，即除以2然後向下取整，此時

A = 9, B = 2, tmp = 3,對剩下的部分繼續快速幂

第二步:

我們發現沒算的那個2是偶數 是以可以得出 3 2 2 2 m o d P 3^{2^{\frac{2}{2}}}modP 3222​modP

顯然 我們可以計算出 A = A × \times × A,然後對B進行右移操作，即除以2然後向下取整，此時A = 81, B = 1, tmp = 3,對剩下的部分繼續快速幂

第三步:

我們發現沒算的那個1是奇數 是以可以得出 3 2 1 − 1 2 m o d P 3^{2^{\frac{1-1}{2}}}modP 3221−1​modP

顯然 我們可以計算出 tmp = tmp × \times × A, A = A × \times × A

然後對B進行右移操作，即除以2然後向下取整，此時A = 729, B = 0, tmp = 243;

第四步:

此時B為0，我們終止循環，傳回tmp % mod即可；

顯然，我們隻是當B為奇數時把結果乘到tmp中，B為偶數時，我們隻将A改變為其的平方即可；這樣就可以加速運算；

我自己的pow_mod

#define long long long
long pow_mod(long a, long b, long mod)
{
    long tmp = 1;
    while(b)
    {
        if(b & 1)
            tmp = ( (tmp % mod) * (a % mod) ) % mod;
        a = ( (a % mod) * (a % mod) ) % mod;
        b >>= 1;
    }
    return tmp;
}
           

快速乘

考慮到在做快速幂的時候 a × \times × a可能會爆long long. 如果你說你要用Java或Python的大整數，那也可以，不過還是建議學一下快速乘；

舉個例子:

20 × \times × 11=20 × \times × (1011)=20 × \times × 2 3 2^{3} 23 × \times × 1 + 20 × \times × 2 2 2^{2} 22 × \times × 0 + 20 × \times × 2 1 2^{1} 21 × \times × 1 + 20 × \times × 2 0 2^{0} 20 × \times × 1 = 160 + 40 + 20 = 220

我們可以看到，每次可以給a乘以2，若目前位為1則代表有貢獻，對答案進行更新，否則就是沒有貢獻，跳過即可；這樣我們每次做的都是 + 操作，是以不必擔心爆long long；時間複雜度是O(logb)

#define long long long
long mul(long a, long b, long mod)
{
    long tmp = 0;
    while(b)
    {
        if(b & 1)
            tmp = (tmp + a) % mod;
        a = (a + a) % mod;
        b >>= 1;
    }
    return tmp % mod;
}
           

題目代碼:

#include <bits/stdc++.h>
using namespace std;

#define long long long
#define INF 0x3f3f3f3f
#define MOD 1000000007
#define MAX_N 200010

long mul(long a, long b, long mod)
{
    long tmp = 0;
    while(b)
    {
        if(b & 1)
            tmp = (tmp + a) % mod;
        a = (a + a) % mod;
        b >>= 1;
    }
    return tmp % mod;
}

long pow_mod(long a, long b, long mod)
{
    long tmp = 1;
    while(b)
    {
        if(b & 1)
            tmp = mul(tmp, a, mod);
        a = mul(a, a, mod);
        b >>= 1;
    }
    return tmp;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    int t;
    cin >> t;
    while(t--)
    {
        long a, b, mod;
        cin >> a >> b >> mod;
        cout << pow_mod(a, b, mod) << endl;
    }

    return 0;
}