第 k 大正整数

问题描述

给定两个数字，分别表示 n 和 k，要求给出无法被 n 整除的第 k 大的正整数。
例如 n = 3, k = 7，则前 7 个无法被 n 整除的正整数为 [1 2 4 5 7 8 10]，答案为 10。

Input

第一行一个整数 T，表示数据组数，不超过 1000。
之后 T 行，每一行给出两个正整数，分别表示 n（2 ≤ n ≤ 1e9）、k（1 ≤ k ≤ 1e9）。

Output

对于每一组数据，输出无法被 n 整除的第 k 大的正整数。

Sample

Input: 
6
3 7
4 12
2 1000000000
7 97
1000000000 1000000000
2 1

Output: 
10
15
1999999999
113
1000000001
1

Limitation

Time limit      1000 ms
Memory limit    262144 kb

解题思路

以 n = 3 为例：

[1 2 (3)][4 5 (6)][7 8 (9)][10 11 (12)][13 14 (15)]...

每一个分组，都是 n - 1 个数 和 一个 n 的倍数组成，由此可以确定 k 的位置：

若 k 是 (n - 1) 的倍数，组数 = k ÷ (n - 1)，否则，组数 = k ÷ (n - 1) + 1；
然后用余数确定 k 的位置：若整除，则 答案 = n × k ÷ (n - 1) - 1，否则，答案 = n × k ÷ (n - 1) + 余数。

源代码

#include <iostream>
using namespace std;

int main() {
	int t;
	cin >> t;
	while (t--) {
		long long n, k;
		cin >> n >> k;
		long long sub = n - 1;
		long long cnt1 = k / sub;
		long long cnt2 = k % sub;
		long long ans = cnt1 * n + cnt2;
		if (cnt2 == 0)
			ans -= 1;
		cout << ans << endl;
	}

	return 0;
}