Py3 C++找出pattern迭代變化解出Leetcode 1015 Smallest Integer Divisible by K

所謂的數論問題，也不一定是是像費馬定理那樣的大問題，能找出數字間的pattern也都是值得玩味的

執行直到 r=(10*r+1)%k==0（其中 k 與 2 和 5 互質），否則返回 -1

[Py3 code請進]

----

So-called number theory problems don't necessarily have to be as big as Fermat's Last Theorem; finding patterns between numbers is also something worth exploring.

do until r=(10*r+1)%k==0 for k coprime to 2, 5 otherwise return -1

[codes on Leetcode]https://leetcode.com/problems/smallest-integer-divisible-by-k/solutions/7372514/r10r1k-for-k-coprime-to-2-5beats-100-by-bdrto/

class Solution:
    def smallestRepunitDivByK(self, k: int) -> int:
        if gcd(10, k)>1: return -1
        X=[1, 11, 111, 1111, 11111, 111111]
        l0=bisect.bisect_left(X, k)
        r=X[l0]%k
        len0=l0+1
        if r==0: return len0
        len0+=1
        while True:
            r=(10*r+1)%k
            if r==0: return len0
            len0+=1

        return -1