K-th Not Divisible by n (Codeforces 1352C)
Tags: Math, binary search

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 \dots$$$. The $$$7$$$-th number among them is $$$10$$$.

Input: The first line contains an integer $$$t$$$ ($$$1 \le t \le 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 \le n \le 10^9$$$) and $$$k$$$ ($$$1 \le k \le 10^9$$$).

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


Sample Inputs:
6
3 7
4 12
2 1000000000
7 97
1000000000 1000000000
2 1

Sample Outputs:
10
15
1999999999
113
1000000001
1

Solution (Python):
t = int(input())

def solve(tmp, n, k):
    if k < tmp:
        return k
    d = k // tmp
    if k % tmp == 0:
        d -= 1
        return n * (d + 1) - 1
    else:
        return n * d + k % tmp
for ss in range(t):
    (n, k) = map(int, input().split())
    print(solve(n - 1, n, k))

Solution (Python):
def find_number(t, s):
    a = []
    for b in s:
        (x, y) = b
        d = (y - 1) // (x - 1) * x + (y - 1) % (x - 1) + 1
        a.append(d)
    return a
t = int(input())
s = []
for _ in range(t):
    s.append(list(map(int, input().split())))
k = find_number(t, s)
for d in k:
    print(d)

Solution (Python):
t = int(input())
for _ in range(t):
    (n, k) = map(int, input().split())
    result = k + (k - 1) // (n - 1)
    print(result)