- 通过研究，偶数乘以任何数都是偶数结尾，所以不会以1结尾。同理5乘以任何数要么是0要么是5. 不会以1结尾。
写出如下代码
if (K % 2 == 0 || K % 5 == 0) return -1;
- 余数的性质
枚举N 从1,11,111，。。。为了防止整数溢出，运用余数定理。
n的变化公式为
初始状态n=0,
递推公式 n = 10 *n + 1;
证明
(10 * n + 1) % K = (10 * (n % K) + 1) % K
=> (10 % K) * (n % K) + (1% K) = (10 % K) * (n % K % K) + (1 % K)
因为 N % K % K = N % K
所以上述等式成立
写出如下代码
int n = 0;
int step = 1;
while (true) {
n = n *10 + 1;
int tmp = n % K;
if (tmp == 0) return step;
step++;
n = tmp;
}
上述有个投机的做法来防止无限循环，就是用个SET，之前出现的过余数再出现，就可以BREAK， RETURN -1。因为进入了轮回，没必要再做下去了。
- 论证必定有解（反证法）
a. K个1（111111...111），下面简写为K（1）。MOD K，假设没有解。那么余数的范围应该【1，K - 1】一共K-1个可能。
b. 从1 开始 到K个1， 每一次取余，一共有K 个 余的结果 。 那么必定有2个结果是相同的。
c. 假设第I次取余 和 第J次取余的结果相同。（i > j）
d. i - j = (i - j) 个 1， j 个0 -> 1111..11 * 100..000
e. 2个数MOD K的余数相同，他们的差 必定能被K整除。
f. 11..1100..00 % K = 0 ， （11..11）% K * (100..00)%K = 0, 因为 if (K % 2 == 0 || K % 5 == 0) return -1; 所以 11..11 % K =0. 与假设矛盾
