Given n pairs of integers, [a_i, b_i], (1\le i\le n), (1\le b_i\le 10^6), find
(\prod_{i=1}^{i=n} \dfrac{a_i}{b_i}) \% p. It is guaranteed that b_i\lt p \forall i \isin [1,n]. It is also guaranteed that (\prod_{i=1}^{i=n} \dfrac{a_i}{b_i}) results in an Integer.
Can anyone explain how to calculate it efficiently, with necessary proof or theorem?
Any help is greatly appreciated.
@galencolin, @ssrivastava990, please help.
Hello @anon74515879 could you please elaborate on the question. as far as i understand you require
(a1a2a3…) choose (b1b2b3…) mod p
where m choose n is the number of ways to choose m of n?
Is this the correct interpretation for the question?
1 Like
No, I guess both aren’t the same.
What essentially required to calculate is,
Given n pairs, [a_i,b_i], let X = \prod_{i=1}^{i=N} a_i
and let Y = \prod_{i=1}^{i=N} b_i, task is to find \dfrac{X}{Y}\%p.
(a/b)%p = (a.b^-1)%p = (a%p.(b^-1%p))%p
b^-1%p is called multiplicative inverse of b modulo p. That is, find a number x such that bx is congruent to 1 modulo p, or simply bx%p=1.
1 Like
Thank you @bal_95, Can you please elaborate the explanation for the actual problem statement?
Even a Code snippet is fine.
@anon74515879 All you need to know for this is how to calculate modular inverse and how modular multiplication is done.
But you haven’t mentioned constraints well eg : you haven’t mentioned constraints for n.
Resource for Modular arithmetic gfg
1 Like
Thank you @pst10.
n is just the size of an array, so it would not be greater than 10^6.
I would also like to mention that a_i is an exponent (written in the form of m^n, n\ge0), which is greater than p.
So, as I understand, we are supposed to calculate (\dfrac {a_i}{b_i})\%p for all i, 1\le i\le N, using Modular division, and take product of all these values using modular multiplication.
Tell me if I am wrong.
Also, I have little ambiguity about Modular Inverse, is (\dfrac{a}{b})\%p same as (a\times b^{p-2})\%p ?
1 Like
Thank you so much @pst10, this made me understand the Concept very clearly, one more help please.
Is it Correct, given P is a prime Integer greater than b?
1 Like