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.
Seems like inverse can only be found when b and n are coprime which is not guaranteed in my case.
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 :).
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
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)