How to calculate ((a1*a2*a3.....*an)/(b1*b2*b3*...bn))mod n

I came across a problem whose answer is in the form of ((a1 x a2 x a3…x an)/(b1 x b2 x b3 x…bn))mod n.

All a and b are very large so actual multiplication and division are not possible.

I know (a x b)%m can be written as ((a%m)x(b%m))%m, but if I simplify using that and do A/B, I’m getting the wrong answer.

Please help me with this.

Update: Forgot to mention that the result of (a1 x a2 x a3…x an)/(b1 x b2 x b3 x…bn) is always a whole number, i.e values of all B’s get cancelled by some A’s.

Check this article: http://www.geeksforgeeks.org/modular-division/

2 Likes

I think you can use prime factorization in this case. As you are saying that the value of (A/B) is a whole number, you can prime factorize a1,a2,… and b1,b2,… . just maintain a count of the prime factors. finally use modular arithmetic to get the answer. I know this might take up some time, but this is on the top of my mind . Anyways happy coding :).

Factorizing the numbers seems doable for numbers <= 10^6 with precomputation. You can precompute largest/smallest factor of each number and hence find the prime factorization in O(number of factors) which is max O(log n)

1 Like

Seems like inverse can only be found when b and n are coprime which is not guaranteed in my case.

I appreciate your response but factorising 10^6 numbers of length 10^6 would take more than just ‘Some time’.

Sorry, didn’t have a look at the constraints