例子 - 如果n = 15且k = 3，答案是：33（3, 6, 9, 12, 13, 15, 18, 21, 23, 24, 27, 30, 31, 32, 33）
我开始按顺序进行，但无法归纳出规律。
对于3的倍数 -> 3+3+3+4+3+3+4+3+3+4
对于包含数字3的数 ->
{
在差异范围为100的范围内 -> 1+1+1+10+1+1+1+1+1+1 = f(n)，这里假设为f(n)；
在差异范围为1000的范围内 -> f(n)+f(n)+f(n)+10*f(n)+f(n)+f(n)+f(n)+f(n)+f(n)+f(n) = ff(n)，这里假设为ff(n)
在差异范围为10000的范围内 -> ff(n) + ff(n) + ff(n) + 10*ff(n)+ff(n) + ff(n) + ff(n)+ff(n) + ff(n) + ff(n)
同样的方法可以延伸下去。
请提供O(n)以上甚至O(1)的更好方法，不要建议使用for循环来检查每个数字。谢谢。
编辑 - 我已经在各处搜索，但无法找到答案，因此这不是重复问题。
j位数 能被 k 整除？[j个9 / k] - [(j-1)个9 / k]j位数 包含数字 k？9 * 10^(k-1) - 8 x 9^(k-1)k 整除，又包含数字 k 的 j位数 数量。但是有多少个呢？k = 2
If k is the rightmost digit, any combination of the previous j-1 digits would work.
Otherwise, only combinations with 0,4,6 or 8 as the rightmost digit would work.
k = 5
If k is the rightmost digit, any combination of the previous j-1 digits would work.
Otherwise, only combinations with 0 or 5 as the rightmost digit would work.
etc.
这个问题可以使用二分查找+数字动态规划来解决......
时间复杂度为o(logn*)
有关解决方案，请参见代码：enter code herehttps://ideone.com/poxhzd
关于גלעד ברקן的回答，如果您有一种O(1)的方法来计算d(j, k) = j以下至少有一个数字k的数字，丢弃可被k整除的数字，那么您可以将e(j, k) = j以下至少有一个数字k或可被k整除的数字计算为j/k + d(j, k)。
这使您能够使用二分查找找到f(n, k)，因为k <= f(n, k) <= k*n并且e(j, k) = n <=> f(n, k) = j：您实际上是尝试猜测哪个j会产生预期的n，在O(log n)次尝试中。
我同意גלעד ברקן的观察结果，即用于有效计算d(j, k)的可整除性规则；但是，它们不容易实现，除了k=5和k=2之外。
我强烈怀疑你能够在这个问题上达到O(log n)的改进；对于某些值的 k，甚至可能无法实现。
这比我想象的要复杂，但我认为我已经想出了最简单情况(k=2)的解决方案。
首先，我尝试通过提出以下问题来简化：序列中哪个位置有数字10^i * k（其中i = 1, 2, 3, ...）？对于k = 2，这些数字是20、200、2000，...
i k n
1 2 20/2 = 10
2 2 200/2 + 2* 5 = 110
3 2 2000/2 + 2* 50 + 18* 5 = 1190
4 2 20000/2 + 2*500 + 18*50 + 162*5 = 12710
i 2 10^i + 2*10^(i-1)/2 + 18*10^(i-2)/2 + 162*10^(i-3)/2 + ?*10^(i-4)/2 + ...
f(i) = 2 * 10^(i-2) - sum(10^(i-x-1)*f(x), x from 2 to i-1) = 2 * 9^(i-2) [thx @m69]
f(2) = 2
f(3) = 2*10 - (1*2) = 18
f(4) = 2*100 - (10*2 + 1*18) = 162
f(5) = 2*1000 - (100*2 + 10*18 + 1*162) = 1458
因此，我们可以使用以下算法：
找到不超过位置的最高数字10^i*2。（如果n在范围[positionOf(10^i*2), positionOf(10^i*2) + (10^i)]内，则我们已经知道解决方案：10^i*2 + (n - positionOf(10^i*2))。例如，如果我们发现i=2，我们知道下一个100个值都在序列中：[201, 300]，所以如果110 <= n <= 210，则解决方案为200+(n-110) = n+90。）
int nn = positionOf(10^i * 2);
int s = 10^i * 2;
for (int ii = i; ii >= 0; ii--) {
for (int j = 1; j < 10; j++) {
if (j == 1 || j == 6) {
if (n <= nn + 10^ii)
return s + nn - n;
nn += 10^ii;
s += 10^ii;
int tmp = positionOf(10^ii);
if (nn + tmp > n)
break;
nn += tmp;
s += 10^ii;
} else {
int tmp = positionOf(10^ii * 2);
if (nn + tmp > n)
break;
nn += tmp;
s += 10^ii * 2;
}
}
}
return s;
这只是未经测试的不完整的伪代码（我知道在Java中不能使用^），ii = 1或0需要被视为特殊情况，这个缺失以及如何找到i也没有显示，否则答案会变得太长。