Modulo problem

general
1

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…

2

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

3

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
4

@nirajs :

Refer to this thread .

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

1 Like
5

(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 bP-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) * bP-2 (mod P)) (mod P).

Now, assuming a1, a2, …, an and b1, b2, …, bn are co-prime to the prime P,

((a1.a2. ... .an) / (b1.b2. ... .bn)) % P
= ((a1.a2. ... .an) * (b1.b2. ... .bn)P-2) % P
        .
        .
        .
= [(a1 % P) * (a2 % P) * ... * (an % P) * (b1P-2 % P) * (b2P-2 % P) * ... * (bnP-2 % P)] % P

NB: This only happens when P is a prime and a1, a2, …, an and b1, b2, …, bn are co-prime to P.

1 Like
6

thanks for the link it was great help…

7

@nirajs : You are most welcome . Cheers , Happy coding .

8

what if P is not prime.?