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. asked 05 Aug '17, 17:54

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 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 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. answered 05 Aug '17, 23:26
1
Thanks for pointing that out, What is the solution then. I tried BigInteger after you mentioned overflow but getting TLE.
(06 Aug '17, 09:49)
I've updated my answer and added the solution explanation. Have a look.
(06 Aug '17, 11:33)
can you explain CRT part in more detail, it just bounce my head.
(07 Aug '17, 21:31)
(08 Aug '17, 06:12)
$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/multiplicativeinverseundermodulom/
(08 Aug '17, 08:39)
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.
(08 Aug '17, 23:17)
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)
(09 Aug '17, 09:33)
showing 5 of 7
show all

@vijju123
check this out.