CSES Problem Set — Exponentiation 題解
===

題目
---
你的任務是有效率地算出 $a^b$ 模 $10^9+7$ 的值。

注意到在這題我們令 $0^0 = 1$。

### 輸入
- 第一行輸入一個整數 $n$，代表計算的個數。（$1 \le n \le 2 \cdot 10^5$）
- 接著有 $n$ 行，每一行有兩個整數 $a$、$b$。（$0 \le a,b \le 10^9$）

### 輸出
輸出 $a^b$ 模 $10^9+7$ 的值。

範例測資
---

Input :
3
3 4
2 8
123 123

Output :
81
256
921450052

想法：快速冪
---
雖然數學告訴我們 $a^b = \exp(b \cdot \log a)$，但機器實現的浮點數運算總有誤差，並不能完美符合數學公式，所以這題我們必須使用整數運算老老實實地乘出結果。

另一方面，這題的 $a$ 與 $b$ 最大都可能到 $10^9$ 這麼多，表示 $a^b$ 的實際值非常有可能超出程式容許的整數上限，先算出 $a^b$ 後再取模也是不實際的。所以我們必須利用以下的數論事實：\\[
(x \times y) \bmod m = ((x \bmod m) \times (y \bmod m)) \bmod m.
\\] 也就是說我們可以在每次乘法之前就先對要運算的數值取模，這樣可以避免運算過程中數值超出限制。

雖然說我們要老老實實地乘出結果，但連續乘 $a$ 乘 $b$ 次（並且取模）並不是最有效率的方式。為了提升運算的效率，我們可以用俗稱「快速冪」的演算法，它只有 $O(\log b)$ 的時間複雜度，比起 $O(b)$ 的直接連乘快上許多。

快速冪只適用於滿足結合律的「乘法」運算 $x \otimes y$。這題的「乘法」可以定義成我們需要的 $(x \times y) \bmod m$，我們可以驗證說這個「乘法」的確滿足結合律。

因為快速冪有不少種寫法，下面的範例程式碼先省略不定義 `fastpow`，後面再把幾種寫法列出來。

### 範例程式碼

#include <iostream>
using namespace std;

int MOD = 1000000007;
int fastpow(int x, int n, int mod);

int main() {
    int n, a, b;
    cin >> n;
    for (int i = 0; i < n; i++) {
      cin >> a >> b;
      cout << fastpow(a, b, MOD);
    }    
}

### 快速冪核心概念

考慮一個滿足結合律的「乘法」運算 $\otimes$，並且把 $n$ 個 $x$「乘」在一起用 $x^n$ 表示。滿足結合律的意思是連續運算時括號順序並不影響結果：\\[
(x \otimes y) \otimes z = x \otimes (y \otimes z).
\\] 而因為「乘法」滿足結合律，所以「次方」也會滿足指數律：\\[
x^{m+n} = x^m \otimes x^n,\quad
x^{mn} = (x^m)^n.
\\] 快速冪的核心概念就是用指數律來降低「乘法」的次數。我們通常會使用 $2$ 來除，比如說把 $x^{14}$ 變成 $(x^7)^2$ 或 $(x^2)^7$。像這樣一直遞迴下去，我們就能用 $O(\log n)$ 次的「乘法」算出 $x^n$。

下面根據拆法的不同分為兩種。

### 快速冪 1：$x^{2k} = (x^k)^2$
例如 $x^{14} = ((x^2 \otimes x)^2 \otimes x)^2$。

這裡使用以下的規則：\\[
x^n = \begin{cases}
1, & n = 0;\\
x^k \otimes x^k, & n = 2k;\\
x^k \otimes x^k \otimes x, & n = 2k+1.
\end{cases}
\\] 並使用遞迴來實現。

> 如果「乘法」沒有單位元素 $x^0$，要把初始條件改成 $n = 1$ 時回傳 $x$。

int fastpow(int x, int n, int mod) {
    if (n == 0)
        return 1;
    int r = fastpow(x, n/2);
    r = (r * r) % mod;
    if (n % 2)
        r = (r * x) % mod;
    return r;
}

### 快速冪 2：$x^{2k} = (x^2)^k$
例如 $x^{14} = x^8 \otimes x^4 \otimes x^2$，其中 $x^{2n}$ 都是從已經算過的 $x^n$「平方」之後算出來的。

這裡使用以下的規則： \\[
x^n = \begin{cases}
1, & n = 0;\\
(x \otimes x)^k, & n = 2k;\\
(x \otimes x)^k \otimes x, & n = 2k+1.
\end{cases}
\\] 並使用遞迴來實現。

> 如果「乘法」沒有單位元素 $x^0$，要把初始條件改成 $n = 1$ 時回傳 $x$。

int fastpow(int x, int n, int mod) {
    if (n == 0)
        return 1;
    int r = fastpow((x * x) % mod, n/2);
    if (n % 2)
        r = (r * x) % mod;
    return u;
}

我們也可以寫成迴圈。這個順序恰好跟遞迴版本顛倒，以 $x^7$ 為例，上面的遞迴版會算 $x^4 \otimes x^2 \otimes x$，而下面的迴圈版是算 $x \otimes x^2 \otimes x^4$。

int fastpow(int x, int n, int mod) {
    int r = 1;
    while (n) {
        if (n % 2)
            r = (r * x) % mod;
        x = (x * x) % mod;
        n /= 2;
    }
    return r;
}