正文
Leetcode 1015. Smallest Integer Divisible by K
小程序：扫一扫查出行【扫一扫了解最新限行尾号】
复制小程序
思路显然是暴力枚举.
但是两个问题:
1.当1的位数非常大时,模运算很费时间,会超时.
其实每次不用完全用'11111...'来%K,上一次的余数*10+1后再%K就行.
证明:
令f(n)=111111...(n个1);
g(n)=f(n)%K
因为f(n)=f(n-1)*10+1
所以f(n)%K=(f(n-1)*10+1)%K
即g(n)=g(n-1)*10+1
2.枚举何时停止?
一种方法是可以设置一个大数,比如10的6次方,可以Accepted.
更精确的方法是:从1个1到K个1,如果这里都没有答案,后面也没了.
因为K的余数不包括0的话有K-1个,我们算了K个,K个里面没有0的话,里面必然至少有两个相等的(抽屉原理),而根据第一个问题所示,相邻的余数有关系,所以一相等之后就是重复循环这些数了,前面找不到后面也肯定没有了.例如K=6:
- 1 % 6 = 1
- 11 % 6 = 5
- 111 % 6 = 3
- 1111 % 6 = 1
- 11111 % 6 = 5
- 111111 % 6 = 3
class Solution:
def smallestRepunitDivByK(self, K: int) -> int:
if K % 2 == 0 or K % 5 == 0:
return -1
g = 0
for i in range(1, K+1):
g = (g * 10 + 1) % K
if g == 0:
return i
return -1
