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 @chefreporter could you please elaborate on the question. as far as i understand you require

(a1*a2*a3…) choose (b1*b2*b3…) mod p

where m choose n is the number of ways to choose m of n?

Is this the correct interpretation for the question?

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.

Thank you @bal_95, Can you please elaborate the explanation for the actual problem statement?

Even a Code snippet is fine.

@chefreporter 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**

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 ?**

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?