发表于 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

• LC 题目链接