given array Numerator[] = { a1 , a2 , a3 … an }

and Denominator[] = { b1 , b2 , b3 … bn }

we have to find ((a1.a2.a3 … an)/(b1.b2.b3 … bn)) % P

given that final value will always be a integer…

given array Numerator[] = { a1 , a2 , a3 … an }

and Denominator[] = { b1 , b2 , b3 … bn }

we have to find ((a1.a2.a3 … an)/(b1.b2.b3 … bn)) % P

given that final value will always be a integer…

((a1%p.a2%p.a3%p…)/(b1%p.b2%p.b3%p…))%p

To calculate (a/b)%m where m is prime NO ,we use multiplicative inverse

If m is a prime number then

(a / b) % m = (a % m * b^(m - 2) % m) % m

For proof see Fermats theorem…

Hope this helps

2 Likes

@nirajs :

Refer to this thread .

http://discuss.codechef.com/questions/4698/use-of-modulo-1000007-in-competitions

1 Like

`(a/b) (mod P) = (a * b`

^{-1}`) (mod P) = (a (mod P) * b`

^{-1} `(mod P)) (mod P)`

.

Now, by Fermat’s theorem, `b`

^{-1} `(mod P)`

will be `b`

^{P-2} `(mod P)`

. Of course, for this `b`

and `P`

must be co-prime to each other and `P`

must be a prime. So, `(a.b) (mod P) = (a (mod P) * b`

^{P-2} `(mod P)) (mod P)`

.

Now, assuming `a`

_{1}, `a`

_{2}, …, `a`

_{n} and `b`

_{1}, `b`

_{2}, …, `b`

_{n} are co-prime to the prime `P`

,

((a_{1}.a_{2}. ... .a_{n}) / (b_{1}.b_{2}. ... .b_{n})) % P = ((a_{1}.a_{2}. ... .a_{n}) * (b_{1}.b_{2}. ... .b_{n})^{P-2}) % P . . . = [(a_{1}% P) * (a_{2}% P) * ... * (a_{n}% P) * (b_{1}^{P-2}% P) * (b_{2}^{P-2}% P) * ... * (b_{n}^{P-2}% P)] % P

NB: This only happens when `P`

is a prime and `a`

_{1}, `a`

_{2}, …, `a`

_{n} and `b`

_{1}, `b`

_{2}, …, `b`

_{n} are co-prime to `P`

.

1 Like

thanks for the link it was great help…

what if P is not prime.?