1. 问题背景与理解Smallest Integer Divisible by K 是 LeetCode 上一道关于数论和模运算的中等难度题目。题目要求找出由数字1组成的最小的正整数使其能够被给定的正整数K整除。例如当K3时答案是111因为111÷337。这类问题在实际应用中可能出现在密码学、哈希算法设计或循环检测等场景。理解这个问题的关键在于掌握模运算的基本性质特别是循环节的概念。2. 核心算法思路2.1 数学原理分析我们需要找到一个由n个1组成的数字N使得N ≡ 0 mod K。这个数字可以表示为 N (10^n - 1)/9因此我们需要找到最小的n使得 (10^n - 1)/9 ≡ 0 mod K 即 10^n ≡ 1 mod 9K根据欧拉定理如果10和9K互质那么解一定存在且n ≤ φ(9K)其中φ是欧拉函数。如果不互质则无解。2.2 算法实现步骤检查K是否为2或5的倍数如果是则无解因为任何由1组成的数都不可能被2或5整除初始化余数r0进行最多K次迭代计算新余数r (10 * r 1) % K如果r 0返回当前迭代次数如果K次迭代后仍未找到解返回-13. C语言实现详解3.1 完整代码实现int smallestRepunitDivByK(int K) { if (K % 2 0 || K % 5 0) { return -1; } int remainder 0; for (int length 1; length K; length) { remainder (remainder * 10 1) % K; if (remainder 0) { return length; } } return -1; }3.2 关键代码解析边界条件检查if (K % 2 0 || K % 5 0) { return -1; }这是基于数学性质任何由1组成的数都不可能被2或5整除。模运算迭代remainder (remainder * 10 1) % K;这个表达式巧妙地避免了直接计算大数而是通过模运算的性质逐步计算余数。终止条件if (remainder 0) { return length; }当余数为0时说明找到了满足条件的数。4. 算法复杂度分析时间复杂度O(K)因为最多进行K次迭代空间复杂度O(1)只使用了常数级别的额外空间实际上根据数学理论解的上限是φ(9K)通常远小于K所以实际运行时间往往比O(K)更好。5. 常见问题与调试技巧5.1 为什么迭代次数限制为K次根据鸽巢原理在K次迭代中余数必然会出现重复。如果前K次迭代都没有找到余数为0的情况则说明无解。5.2 如何处理大数溢出问题这是本题的关键技巧。直接计算由1组成的大数会导致溢出。我们通过模运算的性质只跟踪余数而不是完整的数值新余数 (旧余数 × 10 1) % K5.3 测试用例建议常规情况K1应返回1K3应返回3111÷337K7应返回6111111÷715873边界情况K0根据题目约束K≥1K2或5的倍数应返回-1大质数如K997应返回9966. 算法优化思路虽然这个算法已经相当高效但还可以进一步优化提前终止当余数开始循环时即出现之前出现过的余数可以立即返回-1数学优化利用K的因数分解信息可以更精确地估计解的上限7. 实际应用场景这类算法在以下场景中有实际应用循环小数检测确定分数1/K的循环节长度哈希算法设计需要均匀分布的哈希值时伪随机数生成寻找合适的模数8. 扩展思考这个问题可以扩展到其他进制在b进制下找出由1组成的最小的数能被K整除解法类似只需将代码中的10改为b即可对于特别大的K如1e9以上可以考虑使用快速幂算法来优化模运算过程。