leetcode第129周賽-1015. Smallest Integer Divisible by K，被K整除的最小整數

題目描述：

給定一個正整數K(1<=K<=1e5)，找一個最小整數M(全由1構成，例如1，11，111，11111)，使得該整數能被K整除

求最小正整數M

原題連結：https://leetcode.com/problems/smallest-integer-divisible-by-k/

示例-example：

Example 1:

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

Example 2:

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

Example 3:

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

解決思路：

1）首先很顯然，當K的因數包含2或者5時，不可能找到全為1的正整數M滿足題意。

2）假設K=113，顯然從M=1111開始嘗試，首先餘數remainder=M%K=94。又因為M_next = 11111 = 10 * M + 1，是以有M_next % K = (10 * (M % K) + 1) % K。後面所有依此類推，直到餘數為0(說明找到解)或者餘數出現重複(說明無解)。

3）為了解決餘數重複出現的問題，需要一個list或者set來進行判斷，諸位可以根據自己所掌握的程式設計語言，自行設計這一環節。

Python3代碼：

class Solution:
    def smallestRepunitDivByK(self, K: int) -> int:
        if K%2 == 0 or K%5 == 0:
            return -1
        minlen = 1
        nowrem = 1 % K
        remainderlist = list([])
        while (nowrem != 0) and (nowrem not in remainderlist):
            nowrem = (10 * nowrem + 1) % K
            minlen += 1
        if nowrem == 0:
            return minlen
        else:
            return -1
           

一些體會：

       1）上述代碼實測發現，即使不使用remainderlist來判斷餘數是否出現也能Accepted。由此猜測，要麼是題目給的測試樣例過于友好；要麼可以得到一條數學推論：任意一個正整數K，如果它的餘數不包含2和5，那麼一定可以找到一個全由1組成的數字M，使得M能被K整除。關于這個數學推論，在下感覺挺有意思的，不知道有沒有數學系的大神可以證明下？

       2）最開始不需要判斷K是幾位數，然後找一個恰好不小于K的M。因為M從1開始就一直滿足前面解題思路中所說的規律，是以直接讓M從1開始查找就行了。