难度: Medium
给定正整数 k ，你需要找出可以被 k 整除的、仅包含数字 1 的最 小 正整数 n 的长度。
返回 n 的长度。如果不存在这样的 n ，就返回-1。
注意： n 可能不符合 64 位带符号整数。
示例 1：
输入：k = 1 输出：1 解释：最小的答案是 n = 1，其长度为 1。
示例 2：
输入：k = 2 输出：-1 解释：不存在可被 2 整除的正整数 n 。
示例 3：
输入：k = 3 输出：3 解释：最小的答案是 n = 111，其长度为 3。
提示：
1 <= k <= 105运行时间: 32 ms
内存: 19.9 MB
class Solution:
def smallestRepunitDivByK(self, k: int) -> int:
if k == 1:
return 1
if k % 2 == 0 or k % 5 == 0:
return -1
vis = set()
# 从数字 "1" 开始不断往上扩
sz = 1
mod = 1
vis.add(mod)
for _ in count(2): # 2......
sz += 1
mod = (mod * 10 + 1) % k
if mod == 0:
return sz
if mod in vis:
return -1 # 循环了.
vis.add(mod)
此题解采用模拟方法以寻找由数字1组成的可以被k整除的最小正整数n。首先，对于任何由1组成的整数n，可以表示为如111...1（n个1），也可以表示为数字序列。该算法通过计算模k的余数来避免处理过大的整数。如果k为1，直接返回1因为1可以被1整除。如果k是2或5的倍数，那么不可能存在全1的数字能被k整除，因此返回-1。接着，使用一个集合来存储出现过的余数，从而检测循环。从1开始，逐步增加1的个数，计算每次形成的数模k的余数。如果余数为0，则当前的数就是答案。如果余数已经在集合中出现过，说明开始循环，不存在答案，返回-1。
时间复杂度: O(k)
空间复杂度: O(k)
from itertools import count
class Solution:
def smallestRepunitDivByK(self, k: int) -> int:
if k == 1:
return 1
if k % 2 == 0 or k % 5 == 0: # 2和5的倍数不可能有解
return -1
vis = set()
sz = 1 # 初始化长度为1
mod = 1 # 初始模为1
vis.add(mod)
for _ in count(2): # 从2开始无限计数
sz += 1
mod = (mod * 10 + 1) % k # 生成新的数并取模
if mod == 0:
return sz # 如果模为0，找到答案
if mod in vis:
return -1 # 如果模已经出现过，说明进入循环
vis.add(mod)
任何全为数字1组成的数都可以表示为（10^n - 1）/ 9的形式，其中n是数字1的个数。进一步分析，数字1组成的数在模10运算下的余数总是1，因此如果k是2或5的倍数，即k在模10运算下的余数为0、2、4、5、6、8，这些数无法整除任何以1结尾的数（例如1, 11, 111, ...）。因此，如果k是2或5的倍数，则不存在由数字1组成的数能整除k。
在算法中，通过使用模运算可以有效避免生成和存储大数字。具体来说，每次迭代生成一个新的由1组成的数，我们只保留这个数对k的余数而不是数本身。这样做的原理是基于同余定理，即如果两个数a和b满足a % k == b % k，则a和b在除以k的时候有相同的余数。因此，算法只需要跟踪余数而不是实际的数字，从而大幅度减少了空间和计算需求。
在算法中使用集合来存储每次计算得到的余数。如果在某次迭代中发现新计算的余数已经在集合中，这意味着之前已经有一个相同的余数被计算过，而之后的迭代将会重复之前的模式，形成循环。由于余数开始循环，不会出现新的余数结果，也不可能达到余数为0的情况（即整除情况），因此可以判断出不存在一个全1的数能够被k整除，返回-1。
当k的值非常大时，虽然每次迭代仅生成和比较余数，算法的时间复杂度主要取决于找到余数重复或生成余数0需要的迭代次数。这可能导致性能问题，尤其是在k值接近或等于上限105时。对于优化，可以考虑数学上更高级的方法来预测和跳过部分迭代，或者使用并行处理和优化数据结构来减少查找和存储操作的时间。但是，给定算法的基本逻辑和限制，主要的性能瓶颈在于必须逐一验证每个可能的余数，这限制了大幅度优化的空间。