JZX轻语：简
LeetCode 1015 - 可被K整除的最小整数
发表于2024年06月02日
记r(i)为i个1组成的数字，不难得知r(i) % k = ((r(i-1) % k) * 10 + 1) % k。因此，我们可以不断累加i并计算r(i)的值，直到r(i) % k == 0为止。此外，我们还需要一个哈希表来存储r(i) % k的值，以便在遇到重复的r(i) % k时(意味着后面产生了循环的结果)，直接返回-1。此外，如果k为偶数或者5的倍数，那么不可能找到符合条件的i（所有能整除k的数字不会以1结尾），此时直接返回-1。
class Solution:
def smallestRepunitDivByK(self, k: int) -> int:
seen = set()
if (not k % 2) or (not k % 5): # 提前剪枝: 2和5必定造不了尾部为1的数
return -1
cur_mod = 0
length = 1
while True:
# 1111 = 111 * 10 + 1
# r(digit) % k = ( (r(digit - 1) % k) * 10 + 1 ) % 10
cur_mod = (cur_mod * 10 + 1) % k
if cur_mod == 0:
break
if cur_mod in seen:
return -1
seen.add(cur_mod)
length += 1
return length一开始的做法，不断计算10的幂次方(1111 = 1000 + 100 + 10 + 1)，然后对k取摸并累加到cur_mod中且取摸，直到cur_mod为0为止。实际上，只要简单的对cur_mod乘以10并加1再取摸即可，不需要引入10的幂次方。
class Solution:
def smallestRepunitDivByK(self, k: int) -> int:
if (not k % 2) or (not k % 5):
return -1
cur_mod = 0
cur_digit = 1
length = 1
while True:
digit_mod = cur_digit % k
if length > 1 and digit_mod == 0:
return -1
cur_mod = (cur_mod + digit_mod) % k
if cur_mod == 0:
break
cur_digit *= 10
length += 1
return length