You are given two positive integers n and k. Print the k-th positive integer that is not…
- User
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 ≤ 10^9) and k (1 ≤ k ≤ 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
Assistant
We are given the problem: "You are given two positive integers n and k. Print the k-th positive integer that is not divisible by n." For each test case, find the k-th number that is not divisible by n.
We need to handle up to 1000 test cases. n and k can be up to 1e9. So we need an O(1) solution per test case.
The sequence of numbers not divisible by n: all positive integers except those divisible by n. So it's like the natural numbers skipping every n-th number (multiples of n). The k-th non-divisible number is essentially the k-th integer in the set of numbers where (num % n != 0).
We can derive formula: For a given n, among the first m positive integers, how many are not divisible by n? count_non_divisible(m) = m - floor(m/n). Because floor(m/n) numbers are multiples of n (up to m). We want the smallest m such that count_non_divisible(m) >= k.
So we need to find the smallest integer x such that x - floor(x/n) >= k.
We can use binary search with bounds: low=1, high= something like nk? Actually worst-case: if n is large, say n=1e9, k=1e9, the answer could be around n + k? Let's think: For large n, multiples are sparse, so the k-th non-divisible number is roughly k until k crosses a multiple. The answer is at most n + k? Actually if n=2, then numbers not divisible by 2 are odd numbers. The k-th odd number is 2k -1. That's about 2k. In general, the answer is about something like: each block of n numbers contains (n-1) numbers not divisible by n. So the k-th such number corresponds to block index t = ceil(k/(n-1))? Actually we can derive: The non-divisible numbers occur in groups: for each complete segment of length n, there are n-1 non-divisible numbers. If we let q = floor((k-1)/(n-1)) and r = (k-1) % (n-1), then the answer is q * n + r + 1? Let's test: n=3, n-1=2. For k=7, (k-1)=6, q= floor(6/2)=3, r=0 => answer = 33+0+1=10, correct. For k=1, q=0, r=0 => 0+0+1=1, correct. For n=4, k=12: n-1=3, (k-1)=11, q= floor(11/3)=3, r=2 => answer = 34+2+1=12+3=15, correct? 34=12, +2+1=15. Yes.
But careful: this formula works when n>1 (which is given, n>=2). However, need to check for potential off-by-one errors: For k= n-1? Example n=3, k=2: q=(1)/(2)=0, r=1 => 0+1+1=2, correct. For k=3? Actually n=3, numbers not divisible: 1,2,4,5,7... k=3 => 4. q = floor((3-1)/2) = floor(2/2)=1, r=0 => answer=1*3+0+1=4, correct. For k=4 => 5: q = floor(3/2)=1, r=1 => 3+1+1=5, correct. So seems fine.
But we need to check edge case: when k is exactly a multiple of (n-1)? That is r=0, answer = qn + 1? Example n=3, k=2? Actually multiples of (n-1) are 2,4,6,... For k=2, q= floor(1/2)=0, r=1? Wait (k-1)=1, so q=0, r=1, answer=0+1+1=2, not qn+1. For k=4? (k-1)=3, q=1, r=1? Actually 3/2=1 rem 1, so not r=0. For k=6? (k-1)=5, q=2, r=1? Actually 5/2=2 rem 1. So r never zero? Let's compute: For r to be zero, (k-1) mod (n-1) =0 => k-1 is multiple of n-1 => k = 1 mod (n-1). Actually if (k-1) = q*(n-1) then k = q*(n-1)+1. So when k = 1, (n-1)0+1, q=0, r=0: answer = 0 n +0+1=1. For k = (n-1)+1 = n, e.g., n=3, k=4? Actually (n-1)+1 = 3? For n=3, (n-1)+1=3 => k=3? That gives (k-1)=2, q=1, r=0? Since 2/2=1 rem 0, so yes r=0 => answer = 13+0+1=4. For k=3, numbers: 1,2,4 => third is 4, correct. For n=4, k=4? (n-1)+1=4, (k-1)=3, q=1, r=0 => answer = 14+0+1=5, but let's list n=4 numbers not divisible: 1,2,3,5,6,7,9... Actually 1,2,3,5,6,7,9,10,11,13... So the 4th is 5, correct. So formula works.
Thus answer = ((k-1)//(n-1)) * n + ((k-1) % (n-1)) + 1.
Let's test with sample: n=2, k=1000000000: n-1=1, (k-1)//1 = 999999999, (k-1)%1=0 => answer = 999999999*2 + 0 + 1 = 1999999999, matches sample.
n=1000000000, k=1000000000: n-1=999999999, (k-1)=999999999, // (n-1) = 1, % = 0? Actually 999999999 // 999999999 = 1, remainder 0? Wait careful: (k-1)=999,999,999, n-1=999,999,999 => integer division gives 1, remainder 0? Actually 999,999,999 / 999,999,999 = 1 exactly, so remainder 0. Then answer = 1 * 1000000000 + 0 + 1 = 1000000001, matches sample.
n=7, k=97: n-1=6, (k-1)=96, //6 = 16, %6 = 0? 96/6=16 exactly remainder 0. So answer = 167 + 0 + 1 = 112+1=113? Wait 167=112, +1=113, matches sample.
So formula holds.
We must handle potential overflow? n and k up to 1e9, so (k-1)//(n-1) could be up to about 1e9 when n=2, because n-1=1, division yields k-1 up to 1e9-1, so product with n (which is up to 1e9) yields up to ~1e9 * 1e9 = 1e18, which fits in 64-bit (2^63-1 is about 9.22e18). So 64-bit integer (long long in C++) is fine.
But in Python integers are arbitrary precision, so no problem.
Thus solution: For each test case, read n, k. Compute:
q = (k-1) // (n-1) r = (k-1) % (n-1) ans = q * n + r + 1
Alternatively, we can use the binary search method but this direct formula is simpler.
Double-check for n=2: ans = ((k-1)//1)*2 + (k-1)%1 +1 = (k-1)*2+1 = 2k-1. That's correct for odd numbers.
For n=3, ans = ((k-1)//2)*3 + (k-1)%2 +1, which matches.
Edge Cases: n=10^9, k=1 => (0 // (n-1)=0, r=0 => ans=1. Good.
n=2, k=1 => ans=1.
All good.
Now we need to write code that reads t, then loop and output ans for each.
Complexity O(t).
But is there any nuance? The problem states n >=2. Yes.
Thus answer is straightforward.
We can also derive from equation: x - floor(x/n) = k. The direct formula is equivalent.
Let's confirm with a brute mental: n=5, k=7. List numbers not divisible by 5: 1,2,3,4,6,7,8,9,11... The 7th is 8? Actually list: 1,2,3,4,6,7,8,9,11... Let's count: 1(1),2(2),3(3),4(4),6(5),7(6),8(7). So answer=8. Formula: (k-1)=6, n-1=4, q=6//4=1, r=2? Actually 6//4=1, remainder 2. ans = 1*5+2+1 = 5+3=8, correct.
Thus implementation.
Now, since the problem is from Codeforces (maybe "K-th Not Divisible by n"), the solution is known.
So produce Python code:
def solve(): import sys data = sys.stdin.read().strip().split() if not data: return t = int(data[0]) out = [] idx = 1 for _ in range(t): n = int(data[idx]); k = int(data[idx+1]); idx += 2 q = (k-1) // (n-1) r = (k-1) % (n-1) ans = q * n + r + 1 out.append(str(ans)) sys.stdout.write("\n".join(out))
We could also use formula: ans = k + (k-1)//(n-1) maybe? Let's see: The answer is basically k plus the number of multiples skipped up to that point. The number of multiples skipped is floor((k-1)/(n-1)). Because in the first block of n numbers, there are n-1 non-divisible numbers. The number of complete blocks before the k-th non-divisible is floor((k-1)/(n-1)). Each full block contributes 1 multiple that is skipped, so the answer = k + floor((k-1)/(n-1)). Indeed, test: n=3, k=7: floor((6)/2)=3, ans=7+3=10, correct. n=4, k=12: floor(11/3)=3, ans=12+3=15, correct. n=2, k=1000000000: floor(999999999/1)=999999999, ans=1000000000+999999999=1999999999, correct. n=1000000000, k=1000000000: floor(999999999/999999999)=1, ans=1000000000+1=1000000001, correct. So alternative simpler: ans = k + (k-1)//(n-1). Derivation: answer = qn + r + 1, and k = q(n-1) + r + 1. So answer = qn + (k - q(n-1) - 1) + 1 = qn + k - q(n-1) = k + q*(n - (n-1)) = k + q*1 = k + q. So indeed ans = k + floor((k-1)/(n-1)). This is even simpler and avoids separate r. So we can compute ans = k + (k-1)//(n-1). Check: n=5, k=7: (6)//4=1, ans=7+1=8, correct.
Thus final answer: ans = k + (k-1)//(n-1).
But careful: when n=2, (k-1)//1 = k-1, so ans = k + (k-1) = 2k-1, correct.
When n=3, ans = k + floor((k-1)/2).
So implement that.
Thus the solution is:
for each test case: read n, k ans = k + (k-1)//(n-1) print(ans)
But need to ensure integer division.
Edge: n-1 could be large, but fine.
Thus solve.
Now produce final answer.
But the problem statement: "You are given two positive integers n and k. Print the k-th positive integer that is not divisible by n." Input: first line t, then t lines each with n k.
We need to output each answer on separate line.
We'll provide Python code.
Now, to be safe with large input, use sys.stdin.
Thus final code:
import sys
def main(): data = sys.stdin.read().strip().split() if not data: return t = int(data[0]) out = [] idx = 1 for _ in range(t): n = int(data[idx]); k = int(data[idx+1]) idx += 2 ans = k + (k-1)//(n-1) out.append(str(ans)) sys.stdout.write("\n".join(out))
if name == "main": main()
That solves it.
Now, we need to output the final answer as the code.
But as per instructions: "Your answer should be the solution." So I'll produce the code.
I will also include explanation? The user asked: "You are given two positive integers n and k. Print the k-th positive integer that is not divisible by n." The conversation: "We need to solve this problem." So final answer should be code.
Thus answer: Provide Python solution.
Optionally, we could note that it's O(1) per test case.
Given the sample input and output matches.
Thus final. ```python
import sys
def main() -> None: data = sys.stdin.read().strip().split() if not data: return t = int(data[0]) out = [] idx = 1 for _ in range(t): n = int(data[idx]) k = int(data[idx + 1]) idx += 2 # k-th integer not divisible by n ans = k + (k - 1) // (n - 1) out.append(str(ans)) sys.stdout.write("\n".join(out))
if name == "main": main()