Пожалуйста, подпишитесь на официальный канал Codeforces в Telegram по ссылке https://t.me/codeforces_official. ×

[HELP] Explanation for calculate modular inverse of all number from 1 to N in O(n)

Правка en1, от Libraion, 2020-02-22 06:45:32

I suddenly came across these lines of code when looking at others' submissions: (M is a prime)

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

I tried to google it to understand the formula but ended up finding nothing. So could anyone give me the proof for this?

Thanks a lot <3 <3.

Теги #proof, #help

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en1 Английский Libraion 2020-02-22 06:45:32 415 Initial revision (published)