DIVAB - EDITORIAL

PROBLEM LINK:

Contest
Practice

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)

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 :grin:

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??