题目解析
我们可以拿题面中 n=3n = 3n=3 且 k=5k = 5k=5 去思考,这里的答案是 777。
让我们展开这个序列 1,2,3‾,4,5,6‾,7,8,9‾,10,11,12‾...1,2,\underline{3},4,5,\underline{6},7,8,\underline{9},10,11,\underline{12} ...1,2,3 ,4,5,6 ,7,8,9 ,10,11,12 ...,其中标下划线的数,为 333 的倍数。
我们在算个数的时候,是要忽略 333 的倍数的。
那么我们发现每次经过 n−1n - 1n−1 个数,才会出现一个 nnn 的倍数。
那么我们看一下要经过几次 n−1n - 1n−1 会数到我们想到的数,还是以上面的数举例子。
* 第1轮:1,2,3‾1,2,\underline{3}1,2,3
* 第2轮:4,5,6‾4,5,\underline{6}4,5,6
* 第3轮:7,8,9‾7,8,\underline{9}7,8,9
我们观察,想要数到第 555 个,要数 333 轮,777 在第三轮出现,这个轮次可以直接求得为:⌈kn−1⌉\lceil \frac{k}{n-1} \rceil⌈n−1k ⌉,那么前两轮中每次我们都会少数 111 个。
最终的答案为 k + 轮次 - 1。
AC代码
也可以写成下面这种形式
复杂度
由于我们已经推算出,计算的公式了,所以对于任何情况都是 O(1)O(1)O(1)。