I worked out the mod inverse using GCD and extended euclid.
Then in one answer I saw this:
for(i=2; i<=100000; i++) modInverse[i] = (-(moD/i) * modInverse[moD%i])%moD + moD;
Can someone explain it?
2 Likes
Pls provide a good link !!
Square root decomposition can be thought of as follows. Arrange your numbers in a (square) grid. So thats a ceil(rootN) x ceil(rootN) grid. Now fill in the numbers in row major order, and maintain rowsums. When you need to find sum of range (i…j), divide the range into : i’s row, j’s row, and all rows inbetween. You can find the sum now in time O(length of i’s row) + O(number of rows between i and j) + O(length of j’s row). If your grid is of the rootN x rootN type, all these three will be O(rootN). Thus, such solutions use time complexity O(rootN) per query.
4 Likes
This is new, and fascinating!! Lets get everything (LHS and RHS) “modulo moD” and try to understand it.
The above is basically saying something like, if you write “moD = i * q + r”, then take modulo moD, you get something like 0 = i * q + r => 1/i = -q * 1/r (modulo moD). Since r < i, we would have already computing “1/r” earlier.
Wow, this is amazing - thanks for pointing out!
2 Likes