---
# System prepended metadata

title: 1015. Smallest Repunit Divisible by K
tags: ["medium\_"]

---

# 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. 程式碼

```cpp
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)**

