### grhkm's blog

By grhkm, history, 4 weeks ago,
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

• +139

 » 4 weeks ago, # |   +5 push
 » 4 weeks ago, # |   -15 how to find inverses >_<
•  » » 4 weeks ago, # ^ |   +2 Bruteforce from 1 to p-1 and check if n*i equiv 1 mod pTo 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
•  » » » 4 weeks ago, # ^ | ← Rev. 3 →   0 2nd past wasn't expected :/
•  » » 4 weeks ago, # ^ |   +14 Fermat's little theorem (or ext. Euclidean algorithm).
•  » » » 4 weeks ago, # ^ |   +37 I almost thought you were a different person lol
•  » » » 4 weeks ago, # ^ |   +17 Isn't this fft? SpoilerCreate a polynomial $A(x)=c$, then find it's inverse using FFT?
 » 4 weeks ago, # |   +32 Hello! We are going to learn how to compute inverses mod p. Pre-req: know how to compute inverses mod p
•  » » 4 weeks ago, # ^ |   +8 y e sI'll add "efficiently" then :)
 » 4 weeks ago, # |   +10 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; } 
•  » » 4 weeks ago, # ^ |   +18 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; } 
 » 4 weeks ago, # | ← Rev. 2 →   -9 i read your previous and present blog it's really helpful on me...thanks grhkm
•  » » 4 weeks ago, # ^ |   0 Glad that it helps <3
 » 4 weeks ago, # |   +9 I use the fact that, $inv[i] = fac[i-1] * invfac[i]$
•  » » 4 weeks ago, # ^ |   -10 lol why you got downvotedYeah the method/optimization can be used to precalculate binomial coefficients under n in O(n) :D