# DIVAB - EDITORIAL

Setter: jeevanjyot
Testers: tejas10p, rivalq
Editorialist: hrishik85

1224

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)


there is no need to itarate for finding N+A %B !=0,as A%B!=0 (checked through first condition ) and N%B==0 (checked from second condition) then (N+A)%B=(N%B+A%B)%B=(0+A%B)%B=A%B!=0 from above hence your while loop will end in first check onlyt

5 Likes

Can we have the editorial solution in Java and C++ too? Thanks!

i didn’t understand this part eg 1st test case 5 2 11 :- n = (n/a +1 )*a = (11/5 + 1) *5 = 15
now since 15%2!=0
so 15 = 15+5 = 20
20%2==0
cout<<20;
then how ans came 15??