You are not logged in. Please login at www.codechef.com to post your questions!

×

Problem in solving this problem based on bits and array?

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

arpit728's gravatar image

1★arpit728
6831868
accept rate: 10%

@vijju123

check this out.

(06 Aug '17, 10:30) arpit7281★

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.

link

answered 05 Aug '17, 23:26

c_utkarsh's gravatar image

5★c_utkarsh
1.1k5
accept rate: 17%

edited 07 Aug '17, 23:44

1

@c_utkarsh

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_utkarsh5★

@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_utkarsh5★

@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) c_utkarsh5★
showing 5 of 7 show all
toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • 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