All Inverses at Once — Solution & Editorial

Back to the Problem

Linear recurrence inv[i] = −⌊P/i⌋·inv[P mod i] mod P computes all inverses in O(N) — far faster than N separate Fermat exponentiations.

Complexity: O(N)

Watch out: The recurrence, not N modular exponentiations, is the point — the latter is O(N log P).