I tried to solved THIS PROBLEM on hackerearth, but I am getting wrong answer.This is link to my code please help me in finding what’s wrong with my approach.
Overflow is the problem.
In the function moduloExp(), all the calculations are done modulo M\ (10^{10} + 11).
But, the intermediate result of ans * cnt can be of order M^{2} which is greater than the limit of long.
UPDATE 1:
Note that M = 10^{10} + 11 = 3 \cdot 191 \cdot 17452007 = m_1 \cdot m_2 \cdot m_3. So we can use Chinese Remainder Theorem (CRT) to solve the following system of linear congruences.
x \equiv a_1\ (mod\ m_1)
x \equiv a_2\ (mod\ m_2)
x \equiv a_3\ (mod\ m_3)
The unique solution of this system is x = \sum\ a_i \cdot y_i \cdot z_i \ (mod\ M)
Where, y_i = M / m_i and z_i = y_i^{-1}\ (mod\ m_i).
Usually Euclid’s Extended Algorithm is used to find y^{-1} (as m_1,\ m_2,\ m_3 are pairwise coprime). But in this case you can also use Fermat’s Little Theorem (as m_1,\ m_2,\ m_3 are prime themselves).
The idea in the above approach is to first find the answer mod m_1,\ m_2,\ m_3 (which is easy as they are primes and much smaller than M) and then combine those results to find the answer mod M using CRT.
Here is the accepted solution in C++: https://www.hackerearth.com/submission/10428557/
OR
You can simply use a language that supports big integers (like Python). The builtin function pow(a, b, c) in Python calculates a^{b}\ mod\ c.
Here is the accepted solution in Python: https://www.hackerearth.com/submission/10429278/
UPDATE 2: Detailed Explanation
Let the actual answer be x. We have to find x\ \%\ M (10^{10} + 11). But, since M is too large, the intermediate calculations do not fit in long long.
CRT states that if we know the value of x\ \%\ m_i\ (i = 1,2,...,k), then we can find the value of x\ \%\ M where M = \prod\ m_i = m_1 \cdot m_2\ \cdot \dots\ \cdot m_k. Given that m_1,\ m_2, \dots,\ m_k should be pairwise coprime.
M can be prime factored as M = 3 \cdot 191 \cdot 17452007. So, m_1 = 3,\ m_2 = 191,\ m_3 = 17452007 and these are pairwise coprime.
Find a_1 = x\ \%\ m_1 ,\ a_2 = x\ \%\ m_2,\ a_3 = x\ \%\ m_3.
Now, x\ \%\ M = \sum\ a_i \cdot y_i \cdot z_i \ (mod\ M) (y_i and z_i have already been described above).
To read more about CRT, go through the above link.
1 Like
Thanks for pointing that out, What is the solution then.
I tried BigInteger after you mentioned overflow but getting TLE.
1 Like
I’ve updated my answer and added the solution explanation. Have a look.
z_i = y_i^{-1} (\%\ m_i) means that z_i \times y_i \equiv\ 1\ (\%\ m_i). Here z_i is the modular multiplicative inverse of y_i. You can read about this the following link: http://www.geeksforgeeks.org/multiplicative-inverse-under-modulo-m/
x≡a1 (mod m1)
x≡a2 (mod m2)
x≡a3 (mod m3)
How x could be congurent to a1,a2,a3 can you please simplify it. I am little weak in number theory please explain. I might be getting silly but please help.
Because the mod is different every time. Take x = 20, m1 = 6, m2 = 7, m3 = 8.
Then x = 2 (mod 6), x = 6 (mod 7), x = 4 (mod 8)