PROBLEM LINK:
Setter: jeevanjyot
Testers: tejas10p, rivalq
Editorialist: hrishik85
DIFFICULTY:
1224
PREREQUISITES:
None
PROBLEM:
Determine the smallest number greater than or equal to N which is divisible by A but not divisible by B. Output -1 if no such number exists.
EXPLANATION:
We will output -1 when A \mod B = 0 because in this scenario → there can never be a number which is divisible by A but not by B
For all other cases, we need to find the number larger than N which is divisble by A →
N_{new} =(A \times math.ceil(N \div A))
- If this number is not divisible by B, we output N
- If this number is divisible by B, then we replace N = N + A and keep repeating these 2 steps till we find an N which is not divisible by B
TIME COMPLEXITY:
Time complexity is O(1).
SOLUTION:
Editorialist's Solution
t=int(input())
for _ in range(t):
A, B, N = map(int,input().split())
if A%B==0:
print(-1)
else:
if N%A!=0:
N = (N//A + 1) * A
while N%B==0:
N = N + A
print(N)