1421. A Sum of Fractions, Modulo a Prime

Print a[0]/b[0] + a[1]/b[1] + ... + a[n-1]/b[n-1] modulo a prime p.

n = 3, p = 1000000007, terms 1/2 + 1/3 + 1/6 the exact sum is 1, so the answer is 1

The answer is a single residue, not a fraction. By convention a fraction a/b modulo p means a times the modular inverse of b, which is the unique residue x with b * x = a (mod p).

## What most people try first

Add the fractions exactly, as problems 1415 and 1419 do, and reduce at the end. That is a correct answer to a different question, and it is impossible here: with n at 100 and denominators near 10^9, the common denominator reaches about 10^900, which no fixed-width integer holds. Problem 1419 only works because its denominators are at most 40.

The second attempt computes a / b in integer arithmetic, which is 0 whenever a < b, so the whole sum comes out 0.

## Replace the division by a modular inverse

There is no division modulo p, but there is multiplication by an inverse. Since p is prime and every b[i] is below p, no b[i] is a multiple of p, so Fermat's little theorem gives the inverse directly:

b^(p-1) = 1 (mod p) so inv(b) = b^(p-2) mod p

computed by fast exponentiation in O(log p) multiplications. Then

answer = sum over i of a[i] * inv(b[i]) (mod p)

reducing after every step so nothing grows.

## Why it is correct

Working modulo a prime p means working in a field: every non-zero residue has a multiplicative inverse, and the field operations agree with the rational ones wherever both are defined. Concretely, if the exact sum reduces to N/Dn with Dn not a multiple of p, then

N * inv(Dn) = sum over i of a[i] * inv(b[i]) (mod p)

because the usual algebra of adding fractions is valid in any field, and the reduction from the common denominator to lowest terms only cancels factors that are invertible. So the residue this computes is the image of the exact rational answer, which is what the convention asks for.

The guarantee b[i] < p is what makes every inverse exist. Were a b[i] a multiple of p, the term would have no value modulo p at all, and the answer would not be defined rather than merely hard.

## The boundary that breaks a careless implementation

Computing one inverse per term is O(n log p), which is fine at n = 100. What is not fine is computing a common denominator first and inverting it once: the common denominator overflows. The whole point is that the modular route never needs it.

Also, reduce a[i] and b[i] modulo p before using them. They are below p by the constraints, so it changes nothing here, but writing it costs nothing and is the habit that survives a change of bounds.

## Overflow

Every product is two residues below p, so below about 10^9 each, and the product is near 10^18. That fits a signed 64-bit integer, whose limit is 9223372036854775807, and does not fit a signed 32-bit one, whose limit is 2147483647: a 32-bit build answers 1 as 0 for 1/2 + 1/4 + 1/8 + 1/16 + 1/32 where the truth is 718750006, and answers 437925879 where the truth is 1. In JavaScript 10^18 is past 2^53, so a plain a * b is wrong; the reference splits one factor at 65536 so every intermediate stays below 2^53.

## Cost

O(n log p).

Constraints - `1 ≤ n ≤ 100` - `1 ≤ a[i] ≤ 1000000000` - `1 ≤ b[i] ≤ 1000000000` - `999999937 ≤ p ≤ 1000000009`, `p` is prime, and every `b[i] < p`