正经题解｜不能整除

题目解析

我们可以拿题面中 $n = 3$ 且 $k = 5$ 去思考，这里的答案是 $7$。

让我们展开这个序列 $1,2,\underline{3},4,5,\underline{6},7,8,\underline{9},10,11,\underline{12} ...$，其中标下划线的数，为 $3$ 的倍数。

我们在算个数的时候，是要忽略 $3$ 的倍数的。

那么我们发现每次经过 $n - 1$ 个数，才会出现一个 $n$ 的倍数。

那么我们看一下要经过几次 $n - 1$ 会数到我们想到的数，还是以上面的数举例子。

• 第1轮：$1，2，\underline{3}$
• 第2轮：$4，5，\underline{6}$
• 第3轮：$7，8，\underline{9}$

我们观察，想要数到第 $5$ 个，要数 $3$ 轮，$7$ 在第三轮出现，这个轮次可以直接求得为：$\lceil \frac{k}{n-1} \rceil$，那么前两轮中每次我们都会少数 $1$ 个。

最终的答案为 k + 轮次 - 1。

AC代码

#include <bits/stdc++.h>
using namespace std;
int ceil(int a,int b) {
    return a / b + (a % b > 0);
}
int main() {
    int t,n,k;
    cin >> t;
    while(t--) {
        cin >> n >> k;
        cout << k + ceil(k,n-1) - 1 << endl;
    }
    return 0;
}

也可以写成下面这种形式

#include <bits/stdc++.h>
using namespace std;
int main() {
    int t,n,k;
    cin >> t;
    while(t--) {
        cin >> n >> k;
        cout << k + (k - 1) / (n - 1) << endl;
    }
    return 0;
}

复杂度

由于我们已经推算出，计算的公式了，所以对于任何情况都是 $O(1)$。