Calculate inverse mod p in O(1)! (O(n) pre-computation)

Hello!

We're going to learn how to find inverses mod p today (efficiently).

Pre-req: Know how to find inverses

Main results:

As we know, finding the inverse of n numbers is $$$O(n\log{p})$$$. That is too slow, especially when time limit is tight. Therefore, we want a faster way. I present:

• Find inverse of all numbers between 1 and n in $$$O(n)$$$

• Find inverse of n numbers in $$$O(n + \log{p})$$$

Idea 1:

Notice that $$$p = i \cdot \lfloor \frac{p}{i} \rfloor + (p \% i)$$$. (If you don't know why, compare it to $$$13=3\cdot 4+1$$$)

Now NOTICE that $$$p \% i$$$ is actually less than $$$i$$$. (Big brain mode)

So if we've calculated the inverses of $$$1-(i-1)$$$ already, we can find inverse of $$$(p \% i)$$$. This is what we're going to use.

And therefore, by definition of inverse:

Or to make it easier to read: (Integer division)

So we can calculate inverse of $$$1~n$$$ in $$$O(n)$$$.

Code: (Be aware of overflow) (Also, -(p/i) mod p = (p-p/i) mod p)

int n = 10, p = 1000000007;
int inv[n + 1];
inv[1] = 1;
for (int i = 2; i <= n; i ++) inv[i] = 1LL * (p - p / i) * inv[p % i] % p;

Idea 2:

Our target is $$$O(n+\log p)$$$, so we shall only take inverse once. How?

Let's look at what we want to find:

Let's try to make them have the same denominator!

As we can see, the numerator is a prefix times a suffix, and the denominator is constant. Therefore, we can precompute those and then take inverse of denominator once.

Code:

#include "bits/stdc++.h"
using namespace std;

const long long P = 1000000007;
long long qpow(long long a, long long b) {
	long long ans = 1;
	while (b) {
		if (b & 1) ans = ans * a % P;
		a = a * a % P;
		b >>= 1;
	}
	return ans;
}

long long n, a[1000010], pre[1000010], suf[1000010], pr = 1; // prefix, suffix, product
int main() {
	cin >> n; pre[0] = suf[n + 1] = 1;
	for (int i = 1; i <= n; i ++) cin >> a[i];
	for (int i = 1; i <= n; i ++) {
		pre[i] = pre[i - 1] * a[i] % P;
		suf[n + 1 - i] = suf[n + 2 - i] * a[n + 1 - i] % P;
		pr = pr * a[i] % P;
	}
	pr = qpow(pr, P - 2);
	for (int i = 1; i <= n; i ++) {
		cout << (pre[i - 1] * suf[i + 1] % P) * pr % P << endl;
	}
}

Thank you for reading. If you have any suggestions or any topic you want to learn about I guess I can try writing! If this is helpful vote pls thx