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

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

**Spoiler**

push

how to find inverses >_<

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 ptsLol why did I write in summary

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

I almost thought you were a different person lol

Isn't this fft?

SpoilerCreate a polynomial $$$A(x)=c$$$, then find it's inverse using FFT?

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

Pre-req: know how to compute inverses mod py e s

I'll add "efficiently" then :)

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

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

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

Glad that it helps <3

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

lol why you got downvoted

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

.

Nicely explained, thank you.