算法常見技巧 -快速幂及其相關應用

快速幂

題目

快速幂

典型題例：

給定 n 組 a i a_i ai​, b i b_i bi​, p i p_i pi​，對于每組資料，求出 a i b a_i^b aib​ m o d mod mod p i p_i pi​的值。

示例 ：

2
3 2 5
4 3 9
           

思路

代碼：

/*
核心思路：反複平方法
*/

#include <iostream>
#include <algorithm>

using namespace std;

typedef long long LL;

// a^b % p
int qmi(int a, int b, int p) {

    int res = 1;
    while (b) {
        if (b & 1) res = (LL) res * a % p;
        b >>= 1;
        a = (LL) a * a % p;
    }
    return res;
}

int main() {

    int n;
    scanf("%d", &n);

    while (n --) {
        int a, b, p;
        scanf("%d%d%d", &a, &b, &p);
        printf("%d\n", qmi(a, b, p));
    }

    return 0;
}

           

快速幂求逆元

典型題例：

給定 n n n 組 a i a_i ai​, p i p_i pi​，其中 p i p_i pi​ 是質數，求 a i a_i ai​ 模 p i p_i pi​ 的乘法逆元，若逆元不存在則輸出 impossible。

逆元定義：若整數 b，m 互質，并且對于任意的整數 a，如果滿足 b|a，則存在一個整數 x，使得 a/b≡a×x(modm)，
則稱 x 為 b 的模 m 乘法逆元，記為 b−1(modm)。b 存在乘法逆元的充要條件是 b 與模數 m 互質。
當模數 m 為質數時，bm−2 即為 b 的乘法逆元。

前提n為質數
a / b ≡ a * x (mod n)
兩邊同乘b可得 a ≡ a * b * x (mod n)
即 1 ≡ b * x (mod n)
同 b * x ≡ 1 (mod n)
由費馬小定理可知，當n為質數時
b ^ (n - 1) ≡ 1 (mod n)
拆一個b出來可得 b * b ^ (n - 2) ≡ 1 (mod n)
故當n為質數時，b的乘法逆元 x = b ^ (n - 2)
           

示例 ：

第一行包含整數 n。
接下來 n 行，每行包含一個數組 ai,pi，資料保證 pi 是質數。

輸出共 n 行，每組資料輸出一個結果，每個結果占一行。
若 ai 模 pi 的乘法逆元存在，則輸出一個整數，表示逆元，否則輸出 impossible。

3
4 3
8 5
6 3
           

思路

核心：

當n為質數時，可以用快速幂求逆元：

a / b ≡ a * x (mod n)

兩邊同乘b可得 a ≡ a * b * x (mod n)

即 1 ≡ b * x (mod n)

同 b * x ≡ 1 (mod n)

由費馬小定理可知，當n為質數時

b ^ (n - 1) ≡ 1 (mod n)

拆一個b出來可得 b * b ^ (n - 2) ≡ 1 (mod n)

故當n為質數時，b的乘法逆元 x = b ^ (n - 2)

當n不是質數時，可以用擴充歐幾裡得算法求逆元：

a有逆元的充要條件是a與p互質，是以gcd(a, p) = 1

假設a的逆元為x，那麼有a * x ≡ 1 (mod p)

等價：ax + py = 1

exgcd(a, p, x, y)

代碼：

#include <iostream>
#include <algorithm>

using namespace std;

typedef long long LL;

int n;

int qmi(int a, int b, int p) {
    
    int res = 1;
    while (b) {
        if (b & 1) res = (LL)res * a % p;
        b >>= 1;
        a = (LL) a * a %  p;
    }
    
    return res;
}

int main() {
    
    cin >> n;
    
    while (n --) {
        int a, p;
        scanf("%d%d", &a, &p);
        
        int ans = qmi(a, p - 2, p);
        if (a % p == 0) puts("impossible");
        else printf("%d\n", ans);
    }
    
    return 0;
}

           

充電站

推薦一個零聲學院免費公開課程，個人覺得老師講得不錯，分享給大家：Linux，Nginx，ZeroMQ，MySQL，Redis，fastdfs，MongoDB，ZK，流媒體，CDN，P2P，K8S，Docker，TCP/IP，協程，DPDK等技術内容，立即學習