1376. Every Inverse With One Power

A prime p and n values are given, each strictly between 0 and p. Print the modular inverse of every value, one per line.

n = 4, p = 11 values 2 3 4 5 2*6 = 12 = 1 mod 11 -> 6 3*4 = 12 = 1 mod 11 -> 4 4*3 = 12 = 1 mod 11 -> 3 5*9 = 45 = 1 mod 11 -> 9

The extra rule is the point of the problem: you may use at most one modular exponentiation in total, however large n is.

Problem 1373 inverts the consecutive values 1 to n and uses a recurrence that depends on them being consecutive. These values are arbitrary, so that recurrence does not apply.

## What most people try first

One Fermat power per value, v^(p-2) mod p. It is correct, and at n = 200000 with a modulus near 10^9 it is 200000 exponentiations of about 30 squarings each, roughly 6 million multiplications. That is not fatal, but it is doing the same expensive thing 200000 times when once is enough.

## Invert the whole product once, then unwind

Let P[i] be the product of the first i values, so P[0] = 1 and P[n] is the product of everything. One Fermat power gives inverse(P[n]). Now walk backwards:

cur = inverse(P[n]) for i from n-1 down to 0: answer[i] = cur * P[i] mod p cur = cur * value[i] mod p

## Why it is correct

At the top of each step the invariant is that cur is the inverse of P[i+1], the product of values 0 through i. Then

cur * P[i] = inverse(v0..vi) * (v0..v(i-1)) = inverse(vi)

because the common factors cancel. Multiplying cur by value[i] turns the inverse of v0..vi into the inverse of v0..v(i-1), which restores the invariant one position lower. It holds at the start since cur is the inverse of P[n], so it holds everywhere by induction.

Every inverse exists because p is prime and no value is a multiple of p, which is what the constraint 1 ≤ value < p guarantees. If any value were 0 the product would be 0, which never has an inverse, and the method would produce nonsense rather than report it.

## Overflow

Every product multiplies two values below p, which reaches 10^9 + 7, so the intermediates reach 10^18. A signed 64-bit integer holds that; a 32-bit one stops at 2147483647, and a 32-bit build answers 0 for the large tests here. A JavaScript Number is exact only below 2^53, so the reference splits each factor into 16-bit halves to keep every partial product under 2^53.

## Cost

O(n + log p) multiplications, against O(n log p) for the obvious method.

Constraints - `1 ≤ n ≤ 200000` - `2 ≤ p ≤ 1000000007`, and `p` is prime - `1 ≤ each value ≤ p - 1` - At most one modular exponentiation may be used in total.