×

# Problem in solving this problem based on bits and array?

 0 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 1★arpit728 683●18●68 accept rate: 10% @vijju123 check this out. (06 Aug '17, 10:30) arpit7281★

 1 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. answered 05 Aug '17, 23:26 1.1k●5 accept rate: 17% 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) arpit7281★ I've updated my answer and added the solution explanation. Have a look. (06 Aug '17, 11:33) @c_utkarsh can you explain CRT part in more detail, it just bounce my head. (07 Aug '17, 21:31) arpit7281★ @c_utkarsh can you explain meaning of expression zi=yi−1(mod mi) (08 Aug '17, 06:12) arpit7281★ $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/ (08 Aug '17, 08:39) @c_utkarsh 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) arpit7281★ 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
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×1,664
×856
×398
×344
×235
×153
×77

question asked: 05 Aug '17, 17:54

question was seen: 588 times

last updated: 09 Aug '17, 09:34