Hi,

Please refer this earlier link in codechef below

Has anyone solved POWERMUL using the Chinese Remainder Theorem, as suggested in this very nicely written answer by gamabunta?

Hi,

Please refer this earlier link in codechef below

Has anyone solved POWERMUL using the Chinese Remainder Theorem, as suggested in this very nicely written answer by gamabunta?

Yeah , I did.

For input size N<= 40, i simply pre-computed the exponents of prime factors for each n and stored them.

For N >=40, I used the following approach- For F(N)/F®*F(n-r)keep only either F® or F(n-r) depending

on whether r or n-r <= N/2 and divide the remaining of them from F(n). So , if r=3 and N=8 , we would get = (6^6x7^7x8^8)/(2^2x3^3) .

Now if gcd(F®,M) = 1 ,life is simple as F® and M are co-prime and using extended Euclid ,we can find the answer.

If not , let gcd(F®,M) = x. Now let suppose x contains the prime factors p1,p2 . Extract all the exponents of prime factors from M which occur in x ( let that be y). For eg. let F® be p1xp2xp3xp4 and M = p1^2xp2xp5 ,

then x = p1xp2 and y = p1^2 x p2. So, we are left with y and M/y . Clearly M/y and F® are coprime .

Keep in mind ,that we have divided the larger of F® and F(n-r)(assuming that the smaller one in r) from F(n) and are left with F(n)’(F(n)/F(n-r) ) and F®

.Since **M <= 10^9 and N > 40** , an important observation was that, y would always divide F(n)/(F®*F(n-r)).

So, we are left with F(n)/(n-r) = a, F® = b and F(n)/(F®*F(n-r)) be x.

So. x = 0 (mod y)

and x = a*b^(-1)(mod m/y).

Now you can use CRT

thanks Leon_ken!