Codeforces Round #640 (Div. 4)
翻译 岛田小雅
C. K-th Not Divisible by n
出题人 MikeMirzayanov
有两个正整数 \(n\) 和 \(k\)，输出第 \(k\) 个不能被 \(n\) 整除的正整数。
举个例子，如果 \(n=3\)，\(k=7\)，那么所有的不能被 \(3\) 整除的数是 \(1,2,4,5,7,8,10,13,…\)。这些数里面的第 \(7\) 个是 \(10\)。
输入格式
第一行是一个整型 \(t\) \((1\leqslant{t}\leqslant{1000})\)，代表测试点个数。接下来 \(t\) 行每行一个测试点。
每个测试点给你两个正整型，一个 \(n\) \((2\leqslant{n}\leqslant{10^9})\)，一个 \(k\) \((1\leqslant{k}\leqslant{10^9})\)。
输出格式
对每个测试点输出第 \(k\) 个不能被 \(n\) 整除的正整数。
样例输入
6
3 7
4 12
2 1000000000
7 97
1000000000 1000000000
2 1
样例输出
10
15
1999999999
113
1000000001
1
题解
作者 岛田小雅
样例的第 5 个测试点让我悟到了不得了的东西。
以题目中的 \(3\) 为例，把不能被 \(3\) 整除的数铺开：
\[1,2,4,5,7,8,10,11,13,14,… \]现在把能被 \(3\) 整除的数塞回去：
\[1,2,(3,)4,5,(6,)7,8,(9,)10,11,(12,)13,14,… \]对于 \(3\) 来说，每隔 \(2\) 个数会少一个数。
那对于 \(n\) 来说，就是每隔 \(n-1\) 个数会少一个数。
所以，\(k\) 个数里面少了几个数呢？令缺少的数的数目为 \(x\)，不难得出 \(x=\frac{k}{n-1}\)。那么答案就是 \(k+x\) ——
——了吗？
仔细想想，如果 \(k\) 能被 \(n-1\) 整除，那我们的 \(x\) 就会多算一个。如何避免这种情况呢？
那当然写个条件判断就好啦~（啪）（AC 代码中用了条件运算符）
AC 代码
作者 岛田小雅
#include <bits/stdc++.h>
using namespace std;
int t, n, k;
int main()
{
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
cin >> t;
while(t--)
{
cin >> n >> k;
cout << k+(k%(n-1)?k/(n-1):k/(n-1)-1/*条件运算符*/) << '\n';
}
return 0;
}