1373. Every Inverse At Once

A prime p and a bound n with n < p are given, followed by k indices. For each index i, print the modular inverse of i modulo p, that is the value y in 0 to p-1 with i * y congruent to 1 modulo p.

n = 5, p = 11 indices 1 2 3 4 5 1*1=1 2*6=12 3*4=12 4*3=12 5*9=45 -> 1 6 4 3 9 (45 = 44 + 1, and 44 is 4*11)

## What most people try first

Call the inverse routine once per index. Problem 1327 does it with the extended Euclidean algorithm and problem 1326 does it with Fermat, and both cost O(log p) per index. With k at most 1000 that is fast enough, so why is this a different problem at all?

Because the intended use is the other way round: n reaches 10^6 and the real task behind this one is having EVERY inverse from 1 to n on hand, which is what factorial and inverse-factorial tables need. Doing that with a power per index costs 10^6 * 30 multiplications. There is a way to get all of them in n steps with one multiplication each, and the indices in the input exist only so the answer is short enough to print.

## All of them in one linear pass

inv[1] = 1 for i from 2 to n: inv[i] = (p - (p / i) * inv[p mod i] % p) % p integer division

## Why it is correct

Write q = p / i with integer division and r = p mod i, so p = q*i + r. Read that modulo p:

q*i + r = 0 (mod p)

Multiply both sides by inv[i] * inv[r], which both exist because p is prime and 0 < r < i <= n < p, so neither i nor r is a multiple of p:

q * inv[r] + inv[i] = 0 (mod p) inv[i] = -q * inv[r] (mod p)

And r = p mod i is strictly less than i, so inv[r] was already computed. The recursion is well founded and the loop is a single forward pass.

Two details carry weight. r is never 0, because r = 0 would mean i divides the prime p with 1 < i < p, which is impossible. And the result is negative before repair, which is why the formula subtracts from p.

## Why the modulus must be prime

Every step assumes inv[r] exists. Modulo a composite m, an inverse exists only for values coprime to m, so the chain breaks the first time r shares a factor with m. For m = 12 and i = 5 you get r = 2, and 2 has no inverse modulo 12 at all. When the modulus is composite, use the extended Euclidean algorithm of problem 1327 per value and accept that some values have no answer.

## Overflow

(p / i) * inv[p mod i] multiplies two values below p, so it reaches p^2, which is 10^18 at the stated cap and needs a signed 64-bit integer. In JavaScript that is past the 2^53 a Number holds exactly, and a million BigInt allocations are wasteful, so the reference splits the multiplication into two halves that each stay inside 2^53.

## Cost

O(n) time and O(n) memory for the table, then O(1) per query.

Constraints - `1 ≤ n ≤ 1000000` - `n < p ≤ 1000000007` - `p` is prime - `1 ≤ k ≤ 1000` - `1 ≤ each index ≤ n`