How can I find modular multiplicative inverses of a range in linear time?
№ | Пользователь | Рейтинг |
---|---|---|
1 | tourist | 3947 |
2 | jiangly | 3734 |
3 | Radewoosh | 3646 |
4 | jqdai0815 | 3620 |
4 | Benq | 3620 |
6 | orzdevinwang | 3612 |
7 | ecnerwala | 3581 |
8 | Geothermal | 3569 |
8 | cnnfls_csy | 3569 |
10 | ksun48 | 3479 |
Страны | Города | Организации | Всё → |
№ | Пользователь | Вклад |
---|---|---|
1 | awoo | 162 |
2 | maomao90 | 160 |
3 | nor | 156 |
4 | adamant | 155 |
4 | cry | 155 |
4 | atcoder_official | 155 |
4 | -is-this-fft- | 155 |
8 | maroonrk | 153 |
9 | SecondThread | 147 |
10 | Petr | 146 |
How can I find modular multiplicative inverses of a range in linear time?
Название |
---|
Do you want to find a multiplicative inverse for all numbers from 1 to N — 1?
It can be easily done for a prime N, the idea should be obvious if you'll read about primitive roots modulo N.
For non-prime N the idea should also be similar.
I read about primitive roots that -
If the prime number is p, a primitive root g is a number, that when n goes from [1...p - 1], then gn mod p goes through all the numbers [1...p - 1] in some order.
How do I utilize this further? Sorry but I am unable to really understand how to form a relation between modular inverse and primitive root.
If you thought harder, you'd come up with an idea :).
Due to Fermat's Little Theorem:
.
if the number with respect to which you are finding the modular inverse (i.e. the 'M' in A%M is prime)you can use the Fermat's little theorem according to which the modular inverse of a number with respect to a prime number (say A and P respectively) is pow(A,P-2)
so in one for loop you may find the modular multiplicative inverses of the numbers in the range but the complexity is O(nlogp) as the power function takes log(p) time
http://e-maxx.ru/algo/reverse_element#4 (it's in russian but you can see the code)
Can you please explain the last step before QED in the proof provided?
What have they done after taking mod m on both sides?
They've multiplied both sides of the equality by
r[i] * r[m mod i]
.