Can anyone explain the approach in detail ,i am not able to get it through editorial

This is the problem

https://www.hackerearth.com/practice/math/number-theory/primality-tests/practice-problems/algorithm/little-jhool-and-his-primes/description/?layout=old

the question comes down to-

given a,d,m find x for which (a+dx) ≡ 0(mod m)

so we can write the equation as

dx-my=a

now this is a linear diophantine equation which can be solved easily using extended euclidean algorithm

for any doubts u can check my code-https://github.com/m-e-r-l-i-n/hackerearth-solutions/blob/master/math/number%20theory/primality%20tests/Little%20Jhool%20and%20his%20Primes.java

2 Likes

Thanks bro for help