# 1015. 可被 K 整除的最小整數 ## 題目地址(1015. 可被 K 整除的最小整數) <https://leetcode-cn.com/problems/smallest-integer-divisible-by-k/> ## 題目描述 ``` <pre class="calibre18">``` 給定正整數 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。 首先容易想到的是如果 K 是 2，4，5， 6，8 結尾的話，一定是不行的。直觀的解法是從 1，11，111，1111 。。。 這樣一直除下去，直到碰到可以整除的，我們返回即可。 但是如果這個數字根本就無法整除怎么辦？沒錯，我們會無限循環下去。我們應該在什么時刻跳出循環，返回 - 1 （表示不能整除）呢？ 我們拿題目給出的不能整除的 2 來說。 - 1 // 2 等于 1 - 11 // 2 等于 1 - 111 // 2 等于 1 - ... 我們再來一個不能整除的例子 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`。假如出現了相同的數，我們可以肯定之后會無限循環。比如 153 之后出現了 1，我們可以肯定之后一定是 35。。。 因為我們的 mod 只是和前一個 mod 有關，上面的公式是一個`純函數`。 ## 關鍵點解析 - 數學（無限循環與循環節） ## 代碼 ``` <pre class="calibre18">``` <span class="hljs-title">#</span> <span class="hljs-title"># @lc app=leetcode.cn id=1015 lang=python3</span> <span class="hljs-title">#</span> <span class="hljs-title"># [1015] 可被 K 整除的最小整數</span> <span class="hljs-title">#</span> <span class="hljs-title"># @lc code=start</span> <span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Solution</span>:</span> <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">smallestRepunitDivByK</span><span class="hljs-params">(self, K: int)</span> -> int:</span> <span class="hljs-keyword">if</span> K % <span class="hljs-params">10</span> <span class="hljs-keyword">in</span> [<span class="hljs-params">2</span>, <span class="hljs-params">4</span>, <span class="hljs-params">5</span>, <span class="hljs-params">6</span>, <span class="hljs-params">8</span>]: <span class="hljs-keyword">return</span> - <span class="hljs-params">1</span> seen = set() mod = <span class="hljs-params">0</span> <span class="hljs-keyword">for</span> i <span class="hljs-keyword">in</span> range(<span class="hljs-params">1</span>, K + <span class="hljs-params">1</span>): mod = (mod * <span class="hljs-params">10</span> + <span class="hljs-params">1</span>) % K <span class="hljs-keyword">if</span> mod <span class="hljs-keyword">in</span> seen: <span class="hljs-keyword">return</span> <span class="hljs-params">-1</span> <span class="hljs-keyword">if</span> mod == <span class="hljs-params">0</span>: <span class="hljs-keyword">return</span> ix seen.add(mod) ``` ``` ## 相關題目 - [166. 分數到小數](https://leetcode-cn.com/problems/fraction-to-recurring-decimal/)