线性推逆元

线性求逆元

• 逆元的概念  ax%p == 1 ，x叫a%p下的逆元

• 逆元的用法  在有取模运算时，除法可以被乘以逆元所代替

• 求第i个逆元的时候

• 设p = ki + r (r<i,1<i<p)

• 可以得出ki + r ≡ 0 mod p (p mod p)

• 设i'为i的逆元,r'为r的逆元 (头上带'表示逆元)

• 两边同时乘以i',r'

• 得到 kr' + i' ≡ 0 mod p

• i' = -kr' mod p

• 这时回到上面的定义 k=p/i , r=p mod i

• i' = -p/i * (p mod i)' mod p

•   inv[1]=1;                
    for (int i=2;i<=n;++i)                
        inv[i]=-mod/i*inv[mod%i]%mod,inv[i]=(inv[i]+mod)%mod;