Hello Coders,
I need a little help regarding this small problem.
Given two number a and b and two reminders rem1 and rem2. You need to find all number x which is satisfying following condition.
x%a = rem1 and x%b = rem2
e.g. a=11, b=14, rem1=0, rem2=2 then ans is x=44
I know one simple solution is via for loop but that is not good approach.
Actually I need a formula or some pattern which will give me answer efficiently.
If a and b are coprime, then you can use chinese remainder theorem
Even if a and b are not co prime we can apply CRT on their prime factors, like if we have to find X congruent to p mod a and X congruent to q mod b, and solutions to X, simply express the first one as X congruent to p mod all_prime_factors(a) and as they are coprime with b definitely and each other, apply CRT. This will work if we are guaranteed such X exists(otherwise just check for contradictions and say it is impossible). As we have only O(\log a) prime factors, this is still fast.
Yes, the idea expressed by @nibnalin is what is actually done. I just gave a hint towards the answers. For code, you may look at https://github.com/BidhanRoy/Algorithm-Code-Library/blob/master/Mathematics/Chinese%20Remainder%20Theorem.cpp
clearly
(x-rem1) is divisible by a
also (x-rem2) is divisible by b
now this both are arthematic progressions
find their common terms only is sol.