#640(Div.4)C. K-th Not Divisible by n（数学）

题目描述

You are given two positive integers n and k. Print the k-th positive integer that is not divisible by n.
For example, if n=3, and k=7, then all numbers that are not divisible by 3 are: 1,2,4,5,7,8,10,11,13…. The 7-th number among them is 10.

Input

The first line contains an integer t (1≤t≤1000) — the number of test cases in the input. Next, t test cases are given, one per line.
Each test case is two positive integers n (2≤n≤109) and k (1≤k≤109).

Output

For each test case print the k-th positive integer that is not divisible by n.

Example

input
6
3 7
4 12
2 1000000000
7 97
1000000000 1000000000
2 1
output
10
15
1999999999
113
1000000001
1

题目大意

给定两个数n、k，求第k个不能被n整除的数是多少。

题目分析

首先，我们来想想，从1开始的第k个数本来是k,但因为中间的某一些数不能取，所以答案为k+某个数。我们要求的就是这个数。
以第二组数据为例：
4 12
1,2,3|5,6,7|9,10,11|13,14,15
第12个数是15。前12个数有3个|，所以是12+3=15。所以这个数即为分割线的数量。

分割线的数量不好求，我们可以先求出组数：
因为每组有(n-1)个数，所以组数为k/(n-1)上取整，而分割线的数量即为组数-1，因此答案即为(k+n-1)/(n-1)-1。这个数可以简化为(k-1)/(n-1)。

代码如下

#include <iostream>
#include <cstdio>
#include <cmath>
#include <string>
#include <cstring>
#include <map>
#include <queue>
#include <vector>
#include <set> 
#include <algorithm>
#include <iomanip>
#define LL long long
using namespace std;
int const N=1e5+5;
int main()
{
	int t;
	cin>>t;
	while(t--)
	{
		int n,k;
		cin>>n>>k;
		cout<<k+(k-1)/(n-1)<<endl; 
	}
    return 0;
}