Readme

1015.Smallest-Integer-Divisible-by-K

最直观的想法是分别考察x=1,11,111,...,111111等等，依次查看它们是否能被K整除。但是当x大于九位数的时候就会溢出。这种方法不行。

考虑当前的数是x1且不能被K除尽，那么我们就可以写成x1=K*q+r的形式，其中q是商，r是余数。然后我们会考虑下一个数x2，它可以写成x2=10*x1+1，因此我们可以知道x2 = K*10q+10r+1 ≡ 10r+1 (mod K)。所以我们只要考察10r+1能否被K整除就可以判断x2能否被K整除了。因为r永远是小于K的，这就避免了x1,x2...不断变长带来的溢出问题。

所以此题有点像求小数除法判断是否能整除或者有循环节。不断地更新r=(10r+1)%K，查看结果是否会出现r=0.是的话就意味着对应的x能被K整除。因为根据除法定义r是小于K的，所以当这个过程至多重复K次之后，肯定会重复出现以前曾经有过的r（需要用一个集合记录下来），这就意味着循环节的出现，因此表明永远不可能被K整除，返回-1就可。

当然，从数学上还可以证明，当K%2==0||K%5==0的时候，肯定会有循环节，即无法整除。这里就不给证明过程了。

Leetcode Link