Fombinatorial-POWERMUL with Chinese Remainder Theorem?

general
, , , ,
1

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?

2

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

3

thanks Leon_ken!