grhkm's blog

[Tutorial] Calculate modulo inverses efficiently!
By grhkm, history, 4 years ago, In English
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

Спойлер

  • Vote: I like it
  • +139
  • Vote: I do not like it

Comments Comments (15)
| Write comment?
»
4 years ago, # |
  Vote: I like it +5 Vote: I do not like it

push

→ Reply
»
4 years ago, # |
  Vote: I like it -15 Vote: I do not like it

how to find inverses >_<

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +2 Vote: I do not like it

    Bruteforce from 1 to p-1 and check if n*i equiv 1 mod p

    To do multiplication it's faster to do repeated addition instead. Good luck.

    Please do not downvote, he's troll as seen from contribution pts
    → Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +14 Vote: I do not like it

    Fermat's little theorem (or ext. Euclidean algorithm).

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it +37 Vote: I do not like it

      I almost thought you were a different person lol

      → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it +17 Vote: I do not like it

      Isn't this fft?

      Spoiler
      → Reply
»
4 years ago, # |
  Vote: I like it +32 Vote: I do not like it

Hello! We are going to learn how to compute inverses mod p.

Pre-req: know how to compute inverses mod p

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    y e s

    I'll add "efficiently" then :)

    → Reply
»
4 years ago, # |
  Vote: I like it +10 Vote: I do not like it

By the way, can someone prove the time complexity of this code?

int inv(int i) {
    if(i == 1) return 1;
    return M - (long long) M / i * inv(M % i) % M;
}
→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +18 Vote: I do not like it

    I can't think of a simple proof right now, but using this code, it seems like it runs very fast.

    const int p = 1e9 + 7; // 998244353
int arr[p + 100], n, m;
int main() {
	arr[0] = arr[1] = 1;
	for (int i = 2; i < p; i ++) arr[i] = arr[p % i] + 1, m = max(m, arr[i]);
	cout << m << endl;
}
    → Reply
»
4 years ago, # |
← Rev. 2   Vote: I like it -9 Vote: I do not like it

i read your previous and present blog it's really helpful on me...thanks grhkm

→ Reply
»
4 years ago, # |
  Vote: I like it +9 Vote: I do not like it

I use the fact that, $$$inv[i] = fac[i-1] * invfac[i]$$$

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it -10 Vote: I do not like it

    lol why you got downvoted

    Yeah the method/optimization can be used to precalculate binomial coefficients under n in O(n) :D

    → Reply
»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Nicely explained, thank you.

→ Reply