25.11.25刷题日记 leetcode1015. 可被 K 整除的最小整数
题目链接：1015. 可被 K 整除的最小整数
题目描述：
解题思路
这里的解题思路并不复杂，主要是一些数学推导方面的内容，我们需要利用的主要有抽屉原理，同时还有取模的一些优化。
暴力遍历思路：
首先我们不妨记：
R_{1} = 1,R_{2} = 11,.......,R_n = \underbrace{11\ldots1}_{n\ \text{个}}它满足以下递推关系：
R_1 = 1, \qquad R_{n+1} = 10R_n + 1.取模 k 后，定义
r_n \equiv R_n \pmod{k}.
由递推关系可得
r_1 \equiv 1 \pmod{k}, \qquad r_{n+1} \equiv 10 r_n + 1 \pmod{k}.
首先我们证明取模结果一定是一个循环序列：
序列 \{ r_n \} 的所有可能取值属于有限集合
\{0,1,2,\dots,k-1\}共 k 个状态。由于序列无限，根据抽屉原理，必存在
1 \le i < j \le k+1 [/latex] <p>使得 [katex] r_i = r_j [/katex]</p> <p>由递推关系可写出展开式：</p> [latex] r_j \equiv 10^{\,j-i} r_i + \left( 10^{\,j-i-1} + 10^{\,j-i-2} + \cdots + 10 + 1 \right) \pmod{k}.由于 r_j = r_i，两边相减得
0 \equiv 10^{\,j-i} r_i - r_i + \left( 10^{\,j-i-1} + \cdots + 10 + 1 \right)\pmod{k}.这意味着从第 i 项开始，序列在每隔 $ T = j - i $ 项后重复一次：
r_{n+T} = r_n,\qquad \forall n \ge i.因此序列 \{ r_n \} 为最终周期序列（eventually periodic），周期满足 T \le k 。
上面证明了最后R_i随着i的增加对k的模的结果一定是一个循环序列，所以我们暴力的做法就是：在没出现数字重复前判断是否有R_i mod k == 0。
对应代码：
class Solution:
def smallestRepunitDivByK(self, k: int) -> int:
dict1 = defaultdict(int)
num = 1
len = 1
while num % k != 0:
if dict1[num] != 0:
return -1
dict1[num] = 1
num = (num%k)*10+1
len += 1
return len
优化思路：
由于待除数结尾全都是1组成，显然当k为2或者5的倍数时，此次是一定不能整除的，这里我们直接特判返回即可，那么我们题目的证明就转化为了：
证明当k不为2或者5的倍数时，一定存在某个i使得R_i 可以被k整除
接着上面的抽屉原理，当a>b时，存在
(R_a - R_b)\mod k =0而
R_a - R_b = R_{a-b} * 10^{b}则有：
( R_{a-b} * 10^{b})\mod k = 0由k不为2或者5的倍数可得 k与10互质，不能得其也于10的指数也互质，这里我们不妨设 u为其的乘法逆元，则有：
10^b * u \equiv 1 (\mod k)则有：
R_{a-b} * 10^{b}*u \equiv 0*u(\mod k)则可得：
R_{a-b} \equiv 0(\mod k)即i = a-b时，使得证明成立。
这里证明的好处在于由于我们证明可得除了特判情况外，其他情况一定有解，无需判断是否余数是否有循环了。
对应代码：
class Solution:
def smallestRepunitDivByK(self, k: int) -> int:
if k % 2 == 0 or k % 5 == 0: # 如果 k 是 2 的倍数或者 5 的倍数，返回 -1
return -1
ans, resid = 1, 1 # ans 表示长度，resid 表示余数
while resid % k != 0: # 当余数不为 0 时
resid = (resid % k) * (10 % k) + 1 # 模拟除法运算，计算下一次的余数
ans += 1 # 长度加 1
return ans # 返回最小整数的长度
