• + 1 comment

    In the editorial, I am unable to understant the part where inverse of n is being calculated.

    Precisely, this part =>

    calculate inverses mod p

    for i in xrange(2,p): inv[i] = (p - p/i) * inv[p%i] % p

    I know how to calculate inverse using extended Euler's theorem. It would be nice if you could elaborate the logic behind it or share some link.

    • + 0 comments

      p%i = p - (p/i) * i (by definition of modulo. Note that all division are integer division)

      p%i * inv[i] = p - (p/i) * i * inv[i] = p - (p/i)

      inv[i] = inv[p%i] * p - (p/i)