rahul_1234's blog

Inverse over a range
By rahul_1234, history, 7 years ago, In English

If I want 1/i for 1<=i<=5000000, i.e. inv[i] 

inv[1] = 1;
for (int i=2; i<p; ++i)
	inv[i] = (p - (p/i) * inv[p%i] % p) % p;

I used this but it times out. So I wanted a way for this.

Besides that, if I use fact[i-1]*invfact[i] : would that solve? It is not giving me correct answer so plz tell me what is wrong over here?

  • Vote: I like it
  • -21
  • Vote: I do not like it

Comments Comments (1)
| Write comment?
»
7 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

If p is prime then . You can use BigMod to pre-calculate inverse of factorials in complexity.
Also you can calculate inverse of number from 1 to n is O(n) time and then multiply to pre-calculate inverse of factorials, this will give O(n) complexity.

→ Reply