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

题目描述

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; }