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
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.
Lol 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?
Create 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 p
y 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.