1.线性
ll inv[N]; void init(ll p) { inv[1]=1; for(ll i=2;i<N;i++) inv[i]=(p-p/i)*inv[p%i]%p; }
2.费马小定理：当模数是素数，a^(p-1)=1（mod p） 那么a^(p-2)=a^-1(mod p) ，也就是说a的逆元为a^(p-2)，
当模数不是素数，有欧拉定理 ，a^phi(m)=1（mod m） (a⊥m) ，同理a^-1=a^(phi(m)-1)
1.线性
ll inv[N]; void init(ll p) { inv[1]=1; for(ll i=2;i<N;i++) inv[i]=(p-p/i)*inv[p%i]%p; }
2.费马小定理：当模数是素数，a^(p-1)=1（mod p） 那么a^(p-2)=a^-1(mod p) ，也就是说a的逆元为a^(p-2)，
当模数不是素数，有欧拉定理 ，a^phi(m)=1（mod m） (a⊥m) ，同理a^-1=a^(phi(m)-1)
原文：https://www.cnblogs.com/acjiumeng/p/8438897.html