Little Jhool and his primes

1

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

2

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-hackerearth-solutions/Little Jhool and his Primes.java at master · m-e-r-l-i-n/hackerearth-solutions · GitHub

2 Likes
3

Thanks bro for help