题目：

Given a positive integer k, you need to find the length of the smallest positive integer n such that n is divisible by k, and n only contains the digit 1.

Return the length of n. If there is no such n, return -1.

Note: n may not fit in a 64-bit signed integer.

Example 1:

Input: k = 1
Output: 1
Explanation: The smallest answer is n = 1, which has length 1.

Example 2:

Input: k = 2
Output: -1
Explanation: There is no such positive integer n divisible by 2.

Example 3:

Input: k = 3
Output: 3
Explanation: The smallest answer is n = 111, which has length 3.

Constraints:

1 <= k <= 105

题解：

class Solution {
      public int smallestRepunitDivByK(int k) {
        if (k % 2 == 0 || k % 5 == 0) return -1;
        int r = 0;
        for (int n = 1; n <= k; n++) {
            r = (r * 10 + 1) % k;
            if (r == 0) return n;
        }
        return -1;
    }
}

思路：

首先，如果K的尾数是2，4，5，6，8的话，一定不存在N。简单说明：我们要求的N结尾一定是1，那么一定不能被2的倍数整除。另外我们知道能被5整除的数字的结尾必须是0或者5，所以得证。

然后，我们要证明N的长度不会超过K。

如果这K个余数中有一个余数是0，那么当前的N能被K整除直接返回。
如果这K个余数中都不为0时，一定有重复的余数！我们知道一个数对K的余数只能是0 ~ K - 1其中的一个，所以如果K个数字的余数中没有0，那么肯定有重复的余数。如果出现重复的余数，那么后面再增大N时，对K的余数就会形成循环，则再也不可能出现余数为0的情况。

总之，如果遍历到了长度为K的N时仍然不存在余数是0，那么后面就不用搜索了。

参考：

【LeetCode】1022. Smallest Integer Divisible by K 解题报告（Python）_负雪明烛-CSDN博客

（美服leetcode）1015. Smallest Integer Divisible by K

题目：

题解：

思路：

参考：