# Leetcode 1015. Smallest Integer Divisible by K
###### tags: `Leetcode(C++)`

題目 : https://leetcode.com/problems/smallest-integer-divisible-by-k/ 。

想法 : 題目說n有可能會超過2^64-1，所以用餘數去找就好，類似長除法，如果餘數出現重複就代表循環了。

時間複雜度 : O(n)。

程式碼 :

class Solution {
public:
    int smallestRepunitDivByK(int k) {
        if(k == 1) return 1;
        if(k%2 == 0 || k%5 == 0) return -1;
        
        int ans=1,n=1,same[100010]={0};
        while(n != 0){
            n=(n*10+1)%k; ans++;
            if(same[n] == 1) return -1;
            else same[n]=1;
            
            cout << n << "\n";
        }
        return ans;
    }
};