# 1015. 可被 K 整除的最小整数

### 题目地址(1015. 可被 K 整除的最小整数)

<https://leetcode-cn.com/problems/smallest-integer-divisible-by-k/>

### 题目描述

```
给定正整数 K，你需要找出可以被 K 整除的、仅包含数字 1 的最小正整数 N。

返回 N 的长度。如果不存在这样的 N，就返回 -1。

 

示例 1：

输入：1
输出：1
解释：最小的答案是 N = 1，其长度为 1。
示例 2：

输入：2
输出：-1
解释：不存在可被 2 整除的正整数 N 。
示例 3：

输入：3
输出：3
解释：最小的答案是 N = 111，其长度为 3。
 

提示：

1 <= K <= 10^5
```

### 前置知识

* 循环节

### 公司

* 暂无

### 思路

这道题是说给定一个 K 值，能否找到一个形如 1，11，111，1111 。。。 的数字 n，使得 n % K == 0，并要求 n 尽可能地小。

由于题目要找一个尽可能小的 n ，那么我们可以从小到大进行枚举，直到找到这样的一个 n 值即可。即从 1，11，111，1111 。。。 这样一直除下去，直到碰到可以整除的，我们返回即可。

但是如果这个数字根本就无法整除怎么办？没错，我们会无限循环下去。那么我们应该在什么时刻跳出循环返回 - 1 （表示不能整除）呢？

比如 k = 2 来说我们的算法过程如下：

* 1 // 2 等于 1
* 11 // 2 等于 1
* 111 // 2 等于 1
* ...

如果 k = 6 算法过程如下：

* 1 // 6 等于 1
* 11 // 6 等于 5
* 111 // 6 等于 3
* 1111 // 6 等于 1
* 11111 // 6 等于 5
* ...

通过观察我们发现不断整除的过程，会陷入无限循环，对于 2 来说，其循环节就是 1。对于 6 来说，其循环节来说就是 153。而且由于我们的分母是 6，也就是说余数的可能性一共只有六种情况 0,1,2,3,4,5。

上面是感性的认识， 接下来我们从数学上予以证明。

上面的算法用公式来表示就是`mod = (10 * mod + 1) % K`，其中 mode 为 111xxx111 模 k 的值。假如出现了相同的数，我们可以肯定之后会无限循环。比如 153 之后出现了 1，我们可以肯定之后一定是 35。。。 这是因为我们的 mod 只是和前一个 mod 有关。换句话说就是上面的公式`mod = (10 * mod + 1) % K`是一个`纯函数`，相同的输入输出总是相同的。（也就是说 x mod k 后是 y，下次再碰到 x，继续 mod k 一定还是 y，然后无限循环下去）。

### 关键点解析

* 数学（无限循环与循环节）

### 代码

```py
class Solution:
    def smallestRepunitDivByK(self, K: int) -> int:
        if K % 10 in [2, 4, 5, 6, 8]:
            return - 1
        seen = set()
        mod = 0
        for i in range(1, K + 1):
            mod = (mod * 10 + 1) % K
            if mod in seen:
                return -1
            if mod == 0:
                return ix
            seen.add(mod)
```

### 相关题目

* [166. 分数到小数](https://leetcode-cn.com/problems/fraction-to-recurring-decimal/)


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://leetcode-solution-leetcode-pp.gitbook.io/leetcode-solution/medium/1015.smallest-integer-divisible-by-k.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.