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.

      本题的需求是给定一个数字k，求能够被k整除的数字num的最小长度。并且num只能由数字“1”构成。num=1，11，111，1111......，所以数字的迭代就是num=num*10+1。

     那么对于任意k，计算这个最小的长度时需要分为两部分，一部分是判断是否存在这样的数字，第二部分是返回最小的长度。

     第一次写的时候就卡在如何判断是否存在这样的数字满足整除要求，总不能一直num%k=rem 计算下去，后面发现对于任意的rem，这个0<=rem<k,如果rem=0，则num就符合要求了，同时rem最多就k个，如果rem循环出现了，那么就证明没有任何num能够被k整除。基于这个思路代码就可以写出来了：

     这里还有一点需要注意就是关于num=num*10+1如果直接迭代计算，会出现溢出的问题，有个trick的小技巧。

class Solution {
public:
    int smallestRepunitDivByK(int k) {
        // 1、如何判断一个数永远无法满足条件返回-1 这个有点麻烦 所有余数都出现一遍 则永远无法达到该条件
        // 2、如何计算smallest 的长度 ez
        int  num=1;
        int length=1;
        int dp[100001]={0};
        while((num%k!=0) && dp[num%k]!=1){
            int reminder=num%k;
            num=reminder*10+1;//  num=num*10+1 会溢出
            dp[reminder]=1;
            length++;
        }
        
        if(num%k==0) return length;
        return -1;
    }
};

       接下来对上述代码（num=reminder*10+1;//  num=num*10+1 会溢出）做一个简单的证明。假设 a 为任意数字，且  a 除 k的余数为rem。则有
      a % k = rem ，按照题目要求下一个数字应该为b = 10 * a + 1。则b除k的余数可以求得：
      b % K = (10 * a + 1)%k = (10 % k) * (a % k) + 1 % k = rem * (10 % k) + 1 % K   （1）
      之前分析过，对于任意rem，其数值一定小于k，即k<rem。则rem = rem % k （2）
      将（2）式代入（1）式得到：
      b % K= (rem % k) * (10 % K) + 1 % k= (rem * 10) % K + 1 % 10= (rem * 10 + 1) % k

       所以下一个数字num*10+1 与rem*10+1的余数相同，则代码可以按照如上编写。