# 1922. Count Good Numbers
[1922. Count Good Numbers](https://leetcode.com/problems/count-good-numbers/) (<font color="#FFB800"> Medium</font> 通過率: 49.7%)

## 限制條件
<ul>
<li>1 <= n <= 10^15</li>
</ul>

### 解法 1
第一種方式是照著基本的題意去做出來的結果，想當然一定會有問題，在這裡就遇到 TLE 的問題，所以需要第二種解法。

- 時間複雜度: O(N)
- 空間複雜度: O(1)

class Solution {
public:
    int countGoodNumbers(long long n) {
        long long result = 1;
        bool isOverflow = false;
        for (long i = 0; i < n; i++) {
            if (i % 2 == 1) {
                result *= 4;
            } else {
                result *= 5;
            }
            if (result >= long(pow(10, 9) + 7)) {
                isOverflow = true;
                result = result % long(pow(10, 9) + 7);
            }
        }
        if (isOverflow)
            return result % long(pow(10, 9) + 7);
        return result;
    }
};

### 解法 2
#### 快速冪（Modular Exponentiation）

在這個解法中，我們利用「快速冪」來計算非常大的數的次方模 (mod)，以避免數字過大而造成運算溢位（overflow）或運算速度過慢。換句話說，我們利用 Divide-and-Conquer 的技巧，將原本需要多次相乘的次方運算，透過拆分成更小的次方進行加速。

* 時間複雜度：O(logN)
* 空間複雜度：O(1)

### 詳細步驟

首先，我們要理解如何處理這類問題中的取餘數操作。舉個例子，假設我們需要計算：

5^1000000000 % (10^9 + 7)

這個數字太大了，直接計算會超出電腦能處理的範圍。因此，我們需要利用「快速冪」來避免這個問題。

---

### 什麼是快速冪？

快速冪的核心思想是利用「平方加速」的方式來將次方運算拆分成更小的步驟，這樣不僅能減少運算次數，也能避免數字過大。

我們可以將次方數拆解為二進制數字，然後根據每個二進位位數的值來決定是否需要將結果進行累積。這樣的做法能大幅提升效率，將原本的O(n)運算時間減少為O(logn)。

#### 實作過程：

class Solution {
public:
    long long MOD = 1e9 + 7;

    // modular exponentiation
    long long power(long long base, long long exp) {
        long long result = 1;

        // The base will grow as the exponent (exp) increases.
        base %= MOD;

        while (exp > 0) {
            // If exp % 2 == 1, it means that base^(exp) exists.
            if (exp % 2 == 1) {
                // The base is epual to base^(exp) because exp is equal to 1.
                result = (result * base) % MOD;
            }
            base = (base * base) % MOD;
            exp /= 2;
        }
        return result;
    }
    int countGoodNumbers(long long n) {
        long long evenDigits = (n + 1) / 2;
        long long oddDigits = n / 2;
        long long result = (power(5, evenDigits) * power(4, oddDigits)) % MOD;
        return int(result);
    }
};

### 為什麼這麼做？

- **底數取餘數**：在進行運算之前，我們對底數進行 `base %= MOD` 操作，這樣可以避免在計算過程中出現過大的數字，保持結果在合理範圍內。

- **次方拆解**：每次計算時，我們都將 `exp` 按照二進制方式拆解。當 `exp` 是奇數時，會將結果與 `base` 相乘；然後我們將 `base` 進行平方，並將 `exp` 除以 2。

- **結果取模**：為了避免數字過大，我們每次運算後都對結果取餘數，這樣可以保證計算過程中不會出現溢位，並且保持最終結果在有效範圍內。

---

### 例子解釋

假設我們要計算 `3^13 % (10^9 + 7)`，我們的目標是通過「快速冪」來加速這個過程。首先，13 的二進制表示是 `1101`，表示 `13 = 8 + 4 + 0 + 1`，也就是我們需要計算 `3^8 * 3^4 * 3^1`。

在這個過程中，我們的計算步驟如下：

1. `exp = 13`，是奇數，將 `result` 乘上 `base`（即 `3`），然後平方 `base`，`exp` 除以 2。
2. `exp = 6`，是偶數，跳過乘法，將 `base` 平方，`exp` 除以 2。
3. `exp = 3`，是奇數，將 `result` 乘上 `base`（即 `9^4`），平方 `base`，`exp` 除以 2。
4. `exp = 1`，是奇數，將 `result` 乘上 `base`（即 `81^8`），平方 `base`，`exp` 除以 2。
5. 結束運算，返回 `result`。

每步都進行取餘數操作，防止溢位。