A ledger stores amounts as fractions (num, den). For auditing, each fraction is mapped into arithmetic modulo a prime p: num / den becomes num * inv(den) mod p, where inv(den) is the number with den * inv(den) = 1 (mod p). Return the sum of all mapped fractions modulo p.
Examples
Input: fractions = [(1, 2), (1, 3)], p = 7
Output: 2
Explanation: inv(2) = 4 and inv(3) = 5 mod 7, and 4 + 5 = 9 = 2 (mod 7). Also 1/2 + 1/3 = 5/6 and 5 * inv(6) = 5 * 6 = 30 = 2.
Input: fractions = [(3, 4)], p = 11
Output: 9
Constraints
0 <= len(fractions) <= 2 * 10**4,0 <= num <= 10**18,1 <= den <= 10**18,denis never a multiple ofp.pis prime,2 <= p <= 10**9 + 7.- Target complexity: O(n log p).
Goals
- Express division modulo a prime as multiplication by an inverse
- Compute inverses with Fermat's little theorem and fast powering
- Accumulate the sum without ever using floats