[TUTORIAL] Calculate inverse mod p in O(1)!

Revision en3, by grhkm, 2020-09-27 16:02:46

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

Thank you

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$$$)

$$$p = i \cdot \lfloor \frac{p}{i} \rfloor + (p \% i)$$$
$$$\implies i \cdot \lfloor \frac{p}{i} \rfloor + (p \% i) \equiv 0 \mod p$$$
$$$p \% i \equiv -i \cdot \lfloor \frac{p}{i} \rfloor \mod p$$$

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.

$$$1 \equiv i \cdot (-\lfloor\frac{p}{i}\rfloor \cdot (p\% i)^{-1}) \mod p$$$

And therefore, by definition of inverse:

$$$i^{-1} \equiv (-\lfloor\frac{p}{i}\rfloor \cdot (p\% i)^{-1}) \mod p$$$

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

$$$inv[i] \equiv (-(p/i) \cdot inv[p\% i]) \mod p$$$

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:

$$$\frac{1}{a_1}, \frac{1}{a_2}, \cdots, \frac{1}{a_n} \mod p$$$

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

$$$\frac{a_2a_3\cdots a_n}{a_1a_2\cdots a_n}, \frac{a_1a_3a_4\cdots a_n}{a_1a_2\cdots a_n}, \cdots, \frac{a_1a_2\cdots a_{n-1}}{a_1a_2\cdots a_n} \mod p$$$

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

Spoiler

Tags math, inverse, number-theory

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en5 English grhkm 2020-10-02 22:12:28 15 Tiny change: '\n\n<spoiler' -> '\n<spoiler'
en4 English grhkm 2020-09-27 16:09:56 105
en3 English grhkm 2020-09-27 16:02:46 97
en2 English grhkm 2020-09-27 15:57:18 15
en1 English grhkm 2020-09-27 09:33:17 3437 Initial revision (published)