數據結構與算法學習筆記----快速冪

@@ author: 明月清了個風
@@ first publish time: 2025.1.2

ps??快速冪的兩道模版題，快速冪，乘法逆元，費馬小定理

Acwing 875. 快速冪

[原題鏈接](875. 快速冪 - AcWing題庫)

給定$n$組$a_i,b_i,p_i$，對于每組數據，求出$a_i^{b_i}mod{p}_i$的值

輸入格式

第一行包含整數$n$，

接下來$n$行，每行包含三個整數$a_i,b_i,p_i$。

輸出格式

對于每組數據，輸出一個結果，表示$a_i^{b_i}mod{p}_i$的值。

每個結果占一行。

數據范圍

$1\le n\le 100000$,

$1\le a_i,b_i,p_i\le 2\times 10^9$、

思路

快速冪是一種高效的計算整數冪的算法，適用于大數的冪運算，比如這題的數據范圍，$a_i,b_i,p_i$都可以到億的級別，通過快速冪可以將暴力運算的$O(n)$時間復雜度優化到$O(\log n)$級別，$n$是冪的范圍。

核心思想：將指數$b$通過二進制分解，從而達到$\log b$的運算量，也就是

$$\begin{array}{rl}{a}^{b}modp& =a^{(2^{x_1})+2^{x_2}+?+2^{x_k}}modp\\ & =a^{2^{x_1}}{a}^{2^{x_2}}?a^{2^{x_k}}modp\\ & =(a^{2^{x_1}}modp)?(a^{2^{x_2}}modp)?(a^{2^{x_k}}modp)\end{array}$$

在代碼中，我們也無需對$k$的二進制分解及$a^x$進行預處理，只需要邊運算邊處理就行，具體看下面代碼吧，代碼還是很清晰的。

代碼

#include <iostream>
#include <cstring>using namespace std;typedef long long LL;int qmi(int a, int k, int p)
{int res = 1;while(k)   {if(k & 1) res = (LL) res * a % p;   // 從k的二進制表示最低位開始，也就是2的0次方，此時a的2的0次方就是ak >>= 1;  // 每次右移一位a = (LL) a * a % p;  // 每次將a平方，因為a上面是2的次方，每次提高一位相當于乘一個a的2的0次方，就是a}return res;
}int main()
{int n;cin >> n;while(n --){int a, b, p;cin >> a >> b >> p;cout << qmi(a, b, p) << endl;}return 0;
}

Acwing 876. 快速冪求逆元

[原題鏈接](876. 快速冪求逆元 - AcWing題庫)

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

注意：請返回$0～p?1$之間的逆元。

乘法逆元的定義：

若整數$b，m$互質，并且對于任意的整數$a$，如果滿足$b|a$，則存在一個整數$x$，使得$\frac{a}{b}\equiv a\times x(modm)$，則稱$x$為$b$模$m$的乘法逆元，記為$b^{?1}(modm)$。

$b$存在乘法逆元的充要條件是$b$與模數$m$互質，當模數$m$為質數時，$b^{m?2}$即為$b$的乘法逆元。

輸入格式

第一行包含整數$n$，

接下來$n$行，每行包含一個數組$a_i,p_i$，數據保證$p_i$是質數。

輸出格式

輸出共$n$行，每組數據輸出一個結果，每個結果占一行。

若$a_i$模$p_i$的乘法逆元存在，則輸出一個整數表示逆元，否則輸出impossbile。

數據范圍

$1\le n\le 10^5$，

$1\le a_i,p_i\le 2?10^9$

思路

主要的難點是定義比較繞，我們可以對定義的式子進行一些變形

$$\frac{a}{b}\equiv a\times x(modm)\text{\hspace{1em}(1)}$$

在式(1)的兩邊同乘$b$，我們可以得到式(2)

$$a\equiv b\times a\times x(modm)\text{\hspace{1em}(2)}$$

兩邊再同時除$a$可以得到

$$1\equiv b\times x(modm)\text{\hspace{1em}(3)}$$

因此我們要求的就是一個$x$，可以使$b\times x\equiv 1(modm)$

還有一個注意點是$b$存在乘法逆元的充要條件是模數$m$與$b$互質，題目中給出了條件模數$p_i$保證了是質數，也就是保證了這個條件。

這里需要補充一個額外的定理：費馬小定理

當$m$是一個質數，對于任意整數$a$（$a$不被$m$整除），有$a^{m?1}\equiv 1(modm)$

那么對費馬小定理的這個公式進行變形，拆分次方可得$a?a^{m?2}\equiv 1(modm)$，我們就能直接得到$a$的乘法逆元是$a^{m?2}$。

因此問題轉換為求$a^{m?2}$，也就是應用上面的快速冪。

需要注意的是題目雖然保證了$p$是一個質數，但是卻被沒有保證我們的充要條件，也就是$a_i$與$p_i$互質，因此需要判斷$a_i$是否是$p_i$的倍數，只有這樣的情況他們才不互質。

代碼

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>using namespace std;typedef long long LL;int qmi(int a, int k, int p)
{int res = 1;while(k){if(k & 1) res = (LL) res * a % p;k >>= 1;a = (LL) a * a % p;}return res;
}int main()
{int n;cin >> n;while(n --){int a, p;cin >> a >> p;if(a % p == 0) puts("impossible");else cout << qmi(a, p - 2, p) << endl;}return 0;
}