> For the complete documentation index, see [llms.txt](https://leetcode-solution-leetcode-pp.gitbook.io/leetcode-solution/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://leetcode-solution-leetcode-pp.gitbook.io/leetcode-solution/medium/1015.smallest-integer-divisible-by-k.md). # 1015. 可被 K 整除的最小整数 ### 题目地址(1015. 可被 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/)