企业官网建设流程全解析

1. 这道题到底在问什么

LeetCode上有一类题目，看起来条件简单到令人发指，但真正动手做的时候才发现处处是坑。“可被 K 整除的最小整数”就是典型代表。题目描述大致是这样的：给定一个正整数 K，你需要找出一个最小的正整数 N，使得 N 的每一位都是 1（比如 1、11、111、1111……），并且 N 能被 K 整除。如果不存在这样的数，返回 -1。

我第一次看到这道题的时候，心里想的是：不就是暴力枚举吗？从1开始，1、11、111、1111一直试下去，总能找到吧。结果提交之后直接超时，因为当 K 比较大的时候，这个数字可能长到超出所有整数类型的表示范围。比如 K=999983 这种大质数，答案可能是一个几百位的全1数字，用 long long 根本存不下。

所以这道题的核心难点不在于“怎么判断整除”，而在于两个关键问题：第一，如何在不实际构造出那个巨大数字的前提下判断它是否能被 K 整除；第二，如何确定什么时候应该返回 -1，也就是什么情况下永远找不到这样的数。

这道题适合谁看？如果你正在刷LeetCode，尤其是碰到数学类、同余类题目觉得无从下手，那这篇内容会非常适合你。如果你已经工作了，但想重新梳理一下数论在实际编码中的应用，也能从这里找到一些有用的思路。我会从最朴素的暴力思路讲起，一步步推导到最优解法，把每一步“为什么要这样做”都讲清楚。

2. 从暴力枚举到数学优化：思路演进

2.1 最直觉的暴力解法及其致命缺陷

按照最直接的想法，我们可以用一个变量 num 从1开始，每次循环执行 num = num * 10 + 1，然后判断 num % K == 0。如果等于0，就返回当前数字的位数（或者返回这个数本身，看题目具体要求）。

这个思路在 K 比较小的时候完全没问题。比如 K=3，1%3=1，11%3=2，111%3=0，答案是3位数，返回3或者111都行。K=7的时候，1、11、111、1111、11111、111111，111111%7=0，答案是6位数。

但问题在于，当 K 大到一定程度，num 会迅速膨胀。你可以算一下，每循环一次 num 乘以10再加1，大概循环 n 次之后 num 就有 n 位十进制数。一个 n 位的十进制数需要大约 n*log2(10) ≈ 3.32n 个二进制位来存储。当 n 达到几百的时候，就需要上千个二进制位，这已经远远超出了64位整数的范围。

我实测过，当 K 接近一万的时候，某些情况下答案的位数就已经超过20位了，long long 直接溢出。更不用说 K 可能达到 10^5 甚至更大的情况。所以暴力构造数字这条路，在 K 较大时是走不通的。

2.2 余数递推：不构造大数也能判断整除

关键突破口在于模运算的一个基本性质：我们不需要知道 num 具体是多少，只需要知道 num 对 K 取模的余数就够了。

假设当前全1数字的余数是 rem，那么下一个全1数字（多一位1）可以表示为 当前数字 * 10 + 1。根据模运算的性质：

(a * 10 + 1) % K = ((a % K) * 10 + 1) % K

也就是说，新的余数只依赖于旧的余数，不需要知道原始数字有多大。这样我们就把一个可能无限增长的整数问题，转化成了一个余数递推问题。

具体做法是：维护一个变量 rem，初始值为1（因为第一个全1数字就是1）。然后每次循环执行 rem = (rem * 10 + 1) % K，同时记录当前已经尝试了多少位。如果某次 rem 变成了0，说明找到了答案，返回当前的位数。如果循环了很多次 rem 都没有变成0，那就需要考虑是否存在循环。

这个优化把空间复杂度从“需要存储巨大整数”降到了 O(1)，时间复杂度取决于我们需要循环多少次才能找到答案或者确定无解。

2.3 什么时候应该返回 -1：余数循环的判定

现在问题变成了：我们最多需要循环多少次？如果一直找不到余数为0的情况，怎么判断应该停止？

这里需要用到一个数论上的结论。对于任意正整数 K，全1数字序列对 K 取模的余数序列一定会进入循环。原因很简单：余数的取值范围只有 0 到 K-1 这 K 种可能。根据鸽巢原理，当我们尝试了 K+1 个不同的全1数字之后，必然有两个数字对 K 取模的余数相同。而一旦余数重复出现，由于递推规则是确定性的（给定当前余数，下一个余数唯一确定），后续的余数序列就会完全重复，进入一个循环。

如果在这个循环中没有出现余数为0的情况，那就说明永远不可能找到能被 K 整除的全1数字，应该返回 -1。

那么具体什么情况下会无解呢？这里有一个更精确的数学结论：全1数字能被 K 整除，当且仅当 K 与 10 互质，即 gcd(K, 10) = 1。换句话说，如果 K 含有因子2或者因子5，那么永远找不到能被它整除的全1数字。

为什么？因为全1数字的个位永远是1，它是一个奇数，所以不可能被2整除。同时，全1数字对5取模的结果永远是1（因为个位是1），所以也不可能被5整除。如果一个数 K 含有因子2或因子5，那么任何能被 K 整除的数必须同时能被2或5整除，但全1数字做不到，所以无解。

这个结论非常有用，它让我们可以在开始循环之前就快速判断：如果 K % 2 == 0 或者 K % 5 == 0，直接返回 -1，不需要进入循环。这既节省了时间，也避免了在循环中需要额外判断循环终止条件的问题。

3. 完整代码实现与逐行解析

3.1 核心算法代码

下面是我最终采用的实现方案，用 Python 写的，逻辑清晰，也方便移植到其他语言：

def smallestRepunitDivByK(k: int) -> int: # 如果 K 含有因子 2 或 5，直接无解 if k % 2 == 0 or k % 5 == 0: return -1 rem = 1 # 第一个全1数字 1 对 K 取模的余数 length = 1 # 当前全1数字的位数 while rem != 0: rem = (rem * 10 + 1) % k length += 1 # 根据数论结论，最多循环 K 次一定能找到或进入循环 # 但由于我们已经排除了含因子2和5的情况，一定能找到 if length > k: return -1 return length

这段代码的核心就是那个 while 循环。每次迭代，我们根据当前余数计算出下一个全1数字的余数，同时位数加1。当余数变成0时，当前位数就是答案。

3.2 为什么循环上界是 K

代码中有一个if length > k: return -1的判断。虽然理论上在排除了因子2和5之后一定能找到答案，但加这个判断是为了防止意外情况（比如代码逻辑写错导致死循环）。从数学上分析，余数最多有 K 种可能（0 到 K-1），而我们的递推是确定性的，所以最多经过 K 次迭代，余数序列必然会出现重复。如果在这 K 次迭代中没有出现0，那就永远不会出现0。

不过实际上，由于我们已经提前排除了 K 含有因子2或5的情况，根据数论中的欧拉定理，全1数字一定能被 K 整除，所以这个return -1在正常情况下不会被执行到。它更像是一个安全网。

3.3 几个关键参数的取值分析

让我用几个具体的例子来演示一下这个算法的执行过程，这样你能更直观地理解它是怎么工作的。

例子一：K = 3

• 初始：rem = 1，length = 1
• 第一次循环：rem = (1 * 10 + 1) % 3 = 11 % 3 = 2，length = 2
• 第二次循环：rem = (2 * 10 + 1) % 3 = 21 % 3 = 0，length = 3
• rem 变成0，返回 length = 3

验证：111 能被 3 整除，111 / 3 = 37，正确。

例子二：K = 7

• 初始：rem = 1，length = 1
• 循环1：rem = 11 % 7 = 4，length = 2
• 循环2：rem = 41 % 7 = 6，length = 3
• 循环3：rem = 61 % 7 = 5，length = 4
• 循环4：rem = 51 % 7 = 2，length = 5
• 循环5：rem = 21 % 7 = 0，length = 6
• 返回 6

验证：111111 / 7 = 15873，正确。

例子三：K = 6

• 6 % 2 == 0，直接返回 -1

验证：全1数字都是奇数，不可能被6整除，正确。

例子四：K = 999983（一个大质数）

这个例子用来说明为什么暴力构造数字不可行。999983 是一个质数，且与10互质，所以一定有解。但解的位数可能非常大。用我们的余数递推法，最多循环999983次就能找到答案，每次循环只做一次乘法和一次取模，速度非常快。但如果用暴力构造数字的方法，可能需要构造一个几十万位的整数，内存直接爆炸。

4. 常见问题与排查技巧实录

4.1 为什么我的暴力解法在 K 较小时能过，K 较大时就超时

这是最常见的问题。很多人在初次接触这道题时，会写出类似这样的代码：

num = 1 while num % k != 0: num = num * 10 + 1 return len(str(num))

这段代码在 K 小于1000的时候通常没问题，因为答案的位数不会太多。但当 K 增大时，num 会迅速变成一个巨大的整数，不仅计算速度变慢，而且可能超出语言本身对整数的支持范围（比如 C++ 中的 long long 会溢出）。即使 Python 支持任意精度整数，大整数的乘法和取模运算也会变得非常慢。

解决方案就是前面讲的余数递推法，把“大整数运算”转化为“小整数取模运算”，时间复杂度从 O(n^2) 级别降到 O(n) 级别（n 是答案的位数）。

4.2 为什么 K 含有因子2或5时一定无解

这个问题我在前面已经解释过了，但这里再强调一下，因为这是很多人容易忽略的边界条件。全1数字的个位永远是1，所以它一定是奇数，不可能被2整除。同时，一个数能被5整除当且仅当它的个位是0或5，而全1数字的个位是1，所以也不可能被5整除。

如果一个数 K 含有因子2或因子5，那么任何能被 K 整除的数必须同时含有这些因子。但全1数字不含有因子2和5，所以不可能被 K 整除。这个判断可以在 O(1) 时间内完成，非常高效。

4.3 循环上界到底应该设多少

有些人会把循环上界设成 K，有些人设成 K*2，还有人设成 100000。到底哪个是对的？

从数学上严格来说，由于余数只有 K 种可能，且递推是确定性的，所以最多经过 K 次迭代，余数序列必然重复。如果前 K 次迭代中没有出现0，那就永远不会出现0。所以循环上界设为 K 是安全的。

但需要注意的是，这里的“K 次迭代”是指从初始状态开始算起。在我的代码中，初始 rem=1 对应 length=1，然后每次循环 length 加1。所以当 length 超过 K 时，说明已经尝试了超过 K 个不同的全1数字，根据鸽巢原理，余数必然已经重复过了。此时如果还没有找到0，就可以确定无解。

不过在实际刷题中，由于我们已经提前排除了 K 含有因子2和5的情况，所以循环一定会在 K 次之内找到答案，这个上界判断更多是防御性编程。

4.4 常见问题速查表

4.5 几个容易踩的坑

第一个坑是 K=1 的情况。1 能被 1 整除，所以答案应该是1。有些人的代码在 K=1 时会进入循环，然后 rem 初始为1，判断 rem != 0 不成立，直接跳过循环返回 length=1，这是对的。但如果你的代码逻辑是先执行一次循环再判断，就可能出错。

第二个坑是语言差异。在 C++ 或 Java 中，整数溢出是一个需要特别注意的问题。虽然我们的余数递推法已经避免了构造大整数，但在计算rem * 10 + 1的时候，如果 rem 接近 K 且 K 很大，rem * 10仍然可能溢出 int 范围。比如 K 接近 10^9 时，rem 最大接近 10^9，乘以10就是 10^10，超过了 int 的表示范围。所以在 C++ 中应该使用 long long 来存储 rem，或者在做乘法之前先取模。

第三个坑是返回值。题目要求返回的是全1数字的位数，而不是那个数字本身。有些人在找到余数为0时返回了 rem 或者 num，这是不对的。应该返回 length，也就是当前全1数字有多少位。

5. 从这道题延伸出的数论思维

5.1 同余定理在实际编码中的价值

这道题本质上考察的是同余定理的应用。同余定理告诉我们，如果两个数 a 和 b 对模 m 同余，那么它们在模 m 意义下可以互相替换，而不影响运算结果。这个性质在编码中非常有用，尤其是当我们需要处理超大整数的时候。

举个生活中的例子来帮助理解：假设你有一个时钟，只有12个刻度。现在是3点，过了10个小时之后是几点？你不需要真的去数10个小时，只需要计算 (3 + 10) % 12 = 1，也就是1点。这就是同余的思想——我们只关心“余数”，不关心“完整的大数”。

在这道题中，我们不需要知道全1数字具体是多少，只需要知道它对 K 取模的余数。这样就把一个可能涉及超大整数的问题，转化成了一个只涉及小整数的问题。

5.2 鸽巢原理在算法边界判断中的应用

鸽巢原理（也叫抽屉原理）是判断算法循环边界的一个常用工具。它的核心思想是：如果有 n 个抽屉和 n+1 个物品，那么至少有一个抽屉里放了两个或以上的物品。

在这道题中，余数的取值范围是 0 到 K-1，共 K 个“抽屉”。我们尝试的全1数字序列如果长度超过 K，那么根据鸽巢原理，必然有两个数字对 K 取模的余数相同。由于递推规则是确定性的，余数一旦重复，后续就会进入循环。所以如果前 K 个余数中没有0，那就永远不会出现0。

这个思路在算法题中非常常见。比如在判断链表是否有环的问题中，也是利用类似的原理——如果链表有环，那么快慢指针一定会在某个时刻相遇。理解鸽巢原理，能帮助你在很多看似复杂的问题中快速找到边界条件。

5.3 欧拉定理与存在性证明

虽然在这道题的实际编码中我们不需要用到欧拉定理，但了解它可以帮助你从更深的层次理解为什么当 gcd(K, 10) = 1 时一定有解。

欧拉定理说：如果 a 和 n 互质，那么 a^φ(n) ≡ 1 (mod n)，其中 φ(n) 是欧拉函数，表示小于等于 n 且与 n 互质的正整数的个数。

对于全1数字，它可以表示为 (10^n - 1) / 9。我们要找 n 使得 K 能整除 (10^n - 1) / 9。当 gcd(K, 10) = 1 且 gcd(K, 9) = 1 时，根据欧拉定理，存在 n = φ(9K) 使得 10^n ≡ 1 (mod 9K)，从而 K 能整除 (10^n - 1) / 9。这就证明了解的存在性。

如果 gcd(K, 9) ≠ 1，也就是 K 含有因子3，情况会稍微复杂一些，但结论仍然成立——只要 gcd(K, 10) = 1，就一定有解。这也是为什么我们在代码中只需要排除因子2和5，而不需要排除因子3。

6. 性能对比与优化建议

6.1 不同解法的性能对比

我针对几种不同的解法做了简单的性能测试，用 K=999983 这个质数作为测试用例，结果如下：

可以看到，余数递推法在性能上完全碾压暴力构造法。而且由于我们提前排除了 K 含有因子2和5的情况，实际循环次数通常远小于 K。

6.2 进一步优化的思路

虽然余数递推法已经足够高效，但在某些特殊情况下还可以进一步优化。比如当 K 是质数且 K 与10互质时，答案的位数一定是 K-1 的因子。这个性质可以用来快速缩小搜索范围，但对于刷题来说，直接递推已经足够快了。

另一个优化点是使用快速幂或者矩阵快速幂来计算全1数字的余数，但这对于这道题来说属于过度设计。余数递推法每次迭代只做一次乘法和一次取模，常数极小，已经是最优解了。

6.3 不同语言的实现注意事项

如果你用 C++ 实现，需要注意整数溢出问题。建议使用 long long 来存储 rem，并且在计算(rem * 10 + 1) % k时，如果 k 接近 10^9，rem * 10可能溢出 int，所以要用 long long。

如果你用 Java 实现，同样需要注意 int 溢出。Java 的 int 是32位，最大值约21亿。当 K 接近10^9时，rem 最大接近10^9，乘以10就是10^10，超过 int 范围。所以应该用 long 来存储 rem。

如果你用 Python 实现，基本不需要担心溢出问题，因为 Python 的整数是任意精度的。但要注意 Python 的大整数运算比小整数慢，所以尽量保持 rem 在较小范围内（通过取模实现）。

7. 我在实际刷题中总结的经验

这道题我前前后后做了三次才真正搞明白。第一次直接暴力枚举，结果超时；第二次想到了用余数递推，但忘了处理 K 含有因子2和5的情况，导致死循环；第三次才把所有的边界条件都考虑清楚。

最大的体会是：遇到数学类题目，不要急着写代码，先花几分钟想清楚背后的数学原理。这道题如果不知道“K 含有因子2或5时无解”这个结论，你可能需要写一个复杂的循环终止判断逻辑。但知道了这个结论之后，代码可以写得非常简洁。

另外，余数递推这个技巧在算法题中非常常见。很多涉及“超大整数取模”的题目都可以用类似的思路来解决。比如“找出最小的能被 K 整除的只含数字1和0的数”这道题，也是用余数递推加 BFS 来解决的。掌握这个套路之后，一类题目都能迎刃而解。

最后分享一个小技巧：在写这类题目的时候，我习惯先用几个小数字手动模拟一遍算法流程，确认逻辑正确之后再写代码。比如 K=3、K=7、K=6 这几个例子，覆盖了有解、无解、边界情况三种场景，手动跑一遍就能发现大部分逻辑漏洞。这个习惯帮我省下了很多调试时间。