李在田1. 问题解析：寻找由1组成的最小可被K整除的数
这个问题要求我们找到一个仅由数字1组成的正整数n，使得n能够被给定的正整数k整除，并且这个n是所有满足条件的数中最小的一个。我们需要返回这个最小n的长度（即它包含的1的个数），如果不存在这样的n则返回-1。
举个例子，当k=3时，最小的满足条件的数是111（长度为3），因为111÷3=37。而当k=2时，不存在仅由1组成的数能被2整除，因此返回-1。
1.1 关键约束条件分析
这个问题有几个重要的约束条件需要注意：
- 数字组成限制：n只能由数字1组成，如1, 11, 111, 1111等
- 整除性要求：n必须能被k整除
- 最小长度要求：在所有满足条件的n中，选择长度最短的那个
- 大数问题：n可能非常大，无法用64位整数表示
提示：由于n可能非常大，直接构造n并检查是否被k整除的方法在k较大时会导致整数溢出，因此需要更聪明的数学方法。
需要模型API调用？ 免费领10W Token，多模型网关一键接入 Claude、DeepSeek 等主流模型。
2. 数学原理与算法设计
2.1 模运算的巧妙应用
解决这个问题的关键在于认识到我们不需要存储完整的n值，只需要跟踪n除以k的余数即可。这是因为：
- 如果我们知道当前余数是r，那么下一个由更多1组成的数（即在末尾添加一个1）的余数可以通过公式计算：
code复制新余数 = (老余数 × 10 + 1) % k
这个性质来自于模运算的基本规则：
code复制(a + b) mod m = [(a mod m) + (b mod m)] mod m
(a × b) mod m = [(a mod m) × (b mod m)] mod m
2.2 快速判断无解的情况
我们可以预先排除一些明显无解的情况：
- k是2或5的倍数：任何仅由1组成的数都以1结尾，因此不可能是2或5的倍数（因为能被2整除的数必须以0,2,4,6,8结尾，能被5整除的数必须以0或5结尾）
- k=0：虽然题目中k是正整数，但作为防御性编程可以考虑
2.3 算法终止条件
由于余数的范围是0到k-1，根据鸽巢原理，在最多k次迭代后，余数必定开始重复。因此：
- 如果在k次迭代内余数变为0，则找到解
- 如果经过k次迭代仍未找到余数为0的情况，则可以确定无解
3. C语言实现详解
3.1 完整解决方案代码
c复制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 代码逐行解析
-
无解情况检查：
c复制if (k % 2 == 0 || k % 5 == 0) { return -1; }如果k能被2或5整除，直接返回-1，因为由1组成的数不可能被2或5整除。
-
初始化余数：
c复制int remainder = 0;初始余数为0，表示还没有任何1被添加。
-
主循环：
c复制for (int length = 1; length <= k; length++) { remainder = (remainder * 10 + 1) % k; if (remainder == 0) { return length; } }- 循环从长度1开始，最多尝试k次
- 每次迭代计算新的余数：(老余数×10 + 1) mod k
- 如果余数变为0，返回当前长度
-
无解返回：
c复制return -1;如果循环结束仍未找到解，返回-1
3.3 复杂度分析
- 时间复杂度：O(k)，因为最坏情况下需要循环k次
- 空间复杂度：O(1)，只使用了固定数量的变量
4. 实际测试与边界情况
4.1 测试用例设计
为了验证我们的解决方案，应该考虑以下测试用例：
-
最小k值：
c复制assert(smallestRepunitDivByK(1) == 1); -
无解情况：
c复制assert(smallestRepunitDivByK(2) == -1); assert(smallestRepunitDivByK(10) == -1); -
一般情况：
c复制assert(smallestRepunitDivByK(3) == 3); // 111 ÷ 3 = 37 assert(smallestRepunitDivByK(7) == 6); // 111111 ÷ 7 = 15873 -
较大k值：
c复制assert(smallestRepunitDivByK(999) == 36); assert(smallestRepunitDivByK(9999) == 36);
4.2 边界情况处理
- k=1：最小的解是1，长度为1
- k是质数：可能需要较长的n才能满足条件
- k是最大值(10^5)：确保算法在最大约束下也能高效运行
5. 算法优化与数学证明
5.1 为什么最多只需要检查k次？
根据数论中的鸽巢原理，在模k的情况下，余数只能是0到k-1这k种可能。如果我们检查了k个连续的由1组成的数（即1,11,111,...,11...1[k个1]）的余数，那么：
- 如果其中某个余数为0，我们已经找到解
- 如果没有余数为0，那么根据鸽巢原理，至少有两个不同的数在这个序列中具有相同的余数
假设第i个和第j个数有相同的余数（i<j），那么：
code复制111...1(j个1) - 111...1(i个1) = 111...100...0 (j-i个1，后面i个0)
这个差值可以被k整除。但因为k与10互质（我们已经排除了k是2或5的倍数的情况），所以k必须整除j-i个1组成的数。这意味着存在一个更小的解，与我们假设矛盾。因此，解必定在k次检查内出现。
5.2 性能优化实践
虽然理论复杂度是O(k)，但对于大k（如接近10^5），我们可以进一步优化：
- 提前终止：一旦余数重复出现（而不必等到k次），就可以终止，因为进入了循环
- 记忆化：使用哈希表记录已经出现过的余数
优化后的版本：
c复制int smallestRepunitDivByK(int k) {
if (k % 2 == 0 || k % 5 == 0) return -1;
int remainder = 0;
bool* seen = (bool*)calloc(k, sizeof(bool));
for (int length = 1; length <= k; length++) {
remainder = (remainder * 10 + 1) % k;
if (remainder == 0) {
free(seen);
return length;
}
if (seen[remainder]) {
break; // 进入循环，无解
}
seen[remainder] = true;
}
free(seen);
return -1;
}
6. 常见问题与调试技巧
6.1 为什么我的程序在k很大时运行很慢？
如果直接构造由1组成的数而不是使用模运算，对于大k会导致：
- 整数溢出（即使使用64位整数）
- 大数运算效率低下
解决方案：始终使用模运算来跟踪余数，避免处理大数
6.2 如何处理k=0的情况？
虽然题目保证k是正整数，但防御性编程可以考虑：
c复制if (k <= 0) return -1;
6.3 为什么不需要检查k是否是3的倍数？
与2和5不同，由1组成的数可能被3整除（如111÷3=37）。实际上，任何数字和能被3整除的数都能被3整除，而由n个1组成的数的数字和就是n。因此，当k是3的倍数时，解是否存在取决于是否能找到n使得n是k的倍数。
6.4 调试技巧
- 打印中间结果：在循环中打印每次迭代的余数
c复制printf("Length %d: remainder = %d\n", length, remainder); - 验证小案例：手动计算几个小k值的结果进行验证
- 边界测试：测试k=1, k=最大值的情况
7. 扩展思考与变种问题
7.1 如果允许数字包含0和1？
如果问题放宽限制，允许n由0和1组成（但必须以1开头），算法该如何调整？
解决方案思路：
- 可以使用BFS，每次在末尾添加0或1，并跟踪余数
- 需要记录到达每个余数的最小数字长度
7.2 寻找由其他重复数字组成的最小倍数
例如，寻找由2组成的最小数字能被k整除。如何修改算法？
调整方案：
- 将余数更新公式改为：
(remainder * 10 + digit) % k - 其中digit是重复的数字（如2）
7.3 计算所有满足条件的n的长度
不只是最小的n，而是找出所有长度L，使得由L个1组成的数能被k整除。如何高效计算？
数学方法：
- 找到最小解L0后，其他解都是L0的倍数（在一定条件下）
- 需要更深入的数字理论分析
在实际编程竞赛或面试中，理解这类问题的数学本质并能够应用模运算技巧，是解决大数相关问题的关键。这种"避免直接处理大数，转而使用模运算跟踪余数"的技术，在许多数论问题中都有广泛应用。