# 1015. Smallest Repunit Divisible by K

**題意：**
找最小的 n，使得一個只有 n 個 1 的數（如 1、11、111…）能被 k 整除。
也就是找最小 n，使得：

111...111  (n個1) % k == 0

---

# 1. 直覺理解

repunit 數字會越來越大：

1
11
111
1111
...

如果我們直接用 `long long` → **一定爆掉**。
例如 k = 99991，答案可能需要 99991 位 1，完全不可能用整數存。

---

# 2. 核心想法：只維護「餘數」

定義：

R_n = n 個 1 組成的整數

有遞推：

R_1 = 1
R_2 = R_1 * 10 + 1 = 11
R_3 = R_2 * 10 + 1 = 111

因此模 k 也能遞推（最關鍵）：

rem_{n+1} = (rem_n * 10 + 1) % k

餘數永遠在 0~k-1 範圍 → **永不溢位**。

---

# 3. 快速剪枝（2 和 5 的因數）

repunit 最後一個字是 **1**，因此：

* 不可能被 2 整除
* 不可能被 5 整除

→ 只要 `k % 2 == 0 || k % 5 == 0`
**直接 return -1**

---

# 4. 為什麼最多跑 k 次？

餘數只有 k 種 (0~k-1)，最多 k 次一定開始循環。

如果循環前沒產生 0 → 代表永遠無法整除。

**所以最多跑 k 次就好**。

---

# 5. 程式碼

class Solution {
public:
    int smallestRepunitDivByK(int k) {
        if (k % 2 == 0 || k % 5 == 0) return -1;

        int rem = 0;
        for (int len = 1; len <= k; ++len) {
            rem = (rem * 10 + 1) % k;
            if (rem == 0) return len;
        }
        return -1; 
    }
};

---

# 6. 測試表（常見 k）

| k | repunit 長度 n |
| -- | ------------ |
| 1 | 1 |
| 2 | -1（永不可能） |
| 3 | 3 → 111 |
| 4 | -1 |
| 5 | -1 |
| 6 | -1 |
| 7 | 6 → 111111 |
| 8 | -1 |
| 9 | 9 |
| 10 | -1 |
| 11 | 2 → 11 |
| 12 | -1 |

你列的結果跟標準答案一致（除了你原本程式限制在 10 位數所以會錯）。

---
# 8. 複雜度

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