CF1352 C - K-th Not Divisible by n

This problem is from Codeforces Round #640 (Div. 4) Problem C

Problem

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 \leq t \leq 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 \leq n \leq 10^9)\) and \(k\) \((1 \leq k \leq 10^9)\).

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

Solution

A naive approach would be to loop through each positive integer and check whether each is divisible by \(n\) until the \(k\)-th positive integer which is not divisible by \(n\) is found. This is no good because there is up to \(1000\) test cases and for each one we could be checking around \(10^9\) positive integers which means that this solution is too inefficient and the program will exceed the time limit for this problem.

Idea

What if there was a way to calculate the \(k\)-th positive integer that is not divisible by \(n\) directly without having to loop through each positive integer that comes before it to find it?

Let’s first try to work it out with a simple example, such as when \(n = 3\) and \(k = 7\). To recap, this means that we are trying to find the \(7\)-th number that is not divisible by \(3\).

If we had a list of all the positive integers that are not divisible by \(3\), each number’s position on the list would be equal to its value minus the number of multiples of \(3\) that came before it. For example, \(10\) is in the \(7\)-th position because there are \(3\) multiples of \(3\) before \(10\) i.e. \(3, 6, 9\) and \(7 = 10 - 3\).

Therefore, to find the \(k\)-th positive integer that is not divisible by \(n\), simply add the number of multiples of \(n\) before the \(k\)-th term together with \(k\) i.e. \(3 + 7 = 10\). Next, we have to work out a method to find the number of multiples of \(n\) before the \(k\)-th term.

I noticed that I can do this by dividing \(k-1\) by \(n - 1\). For instance when \(n = 3\) and \(k = 7\), \((7-1)/(3-1) = 6/2 = 3\) and there are \(3\) multiples of \(3\) before the \(7\)-th term which is \(10\).

My Code

#include <bits/stdc++.h>

using namespace std;

int main() {
	int t; cin >> t;
	for (int i = 0; i < t; i++) {
		int n, k; cin >> n >> k;
		int x = (int) (k-1) / (n-1); // number of multiples of n before the k-th term
		printf("%d\n", k + x);
	}
	return 0;
}

If you have any corrections, suggestions, or feedback, please feel free to email them to beaux@codesunji.com. I’d love to hear back from you and improve this site in any way I can :]