设 i n v [ i ] inv[i] inv[i]表示 i i i模 m m m的逆元
t = m / i , k = m t=m/i,k=m%i t=m/i,k=m
t ∗ i + k = 0 ( m o d m ) t*i+k=0(mod m) t∗i+k=0(modm)
− t ∗ i = k ( m o d m ) -t*i=k(mod m) −t∗i=k(modm)
同除以 i ∗ k i*k i∗k
− t ∗ i n v [ k ] = i n v [ i ] ( m o d m ) -t*inv[k]=inv[i](mod m) −t∗inv[k]=inv[i](modm)
i n v [ i ] = ( m − m / i ) ∗ ( i n v [ m % i ] ) % m inv[i]=(m-m/i)*(inv[m\%i])\%m inv[i]=(m−m/i)∗(inv[m%i])%m