逆元求法
时间复杂度T(n)：O(log2n);
空间复杂度S(n)：O(n);
去搜罗了一些关于逆元的各种优秀的求取方式，在下面列举出来
前置技能：欧几里得 & 扩展欧几里得
/*O(log n) 欧几里得, (最大公约数)*/ long long gcd(long long a, long long b) { return b ? gcd(b, a % b) : a; } /*O(log n) 扩欧 [ax mod b = 1]*/ long long x, y; inline void ext_gcd(long long a, long long b, long long &x, long long &y) { b ? (ext_gcd(b, a % b, y, x), y -= (a / b) * x) : (x = 1, y = 0); }
逆元1 ：O(logn)针对单个数字a，求a 在 %p 意义下的逆元（gcd(a,p)要等于1）
inline long long get_inv1(long long a, long long mod) { ext_gcd(a, mod, x, y); return (x % mod + mod) % mod; }
证明：略
逆元2：O(n)预处理阶乘和逆元
/*O(n)阶乘求逆元 + 预处理阶乘*/ inline void get_inv2(const int &n, const int &mod) { fac[0] = fac[1] = 1; for (int i = 2; i <= n; ++i) fac[i] = fac[i - 1] * i % mod; ext_gcd(fac[n], mod, x, y); inv[n] = (x % mod + mod) % mod; for (int i = n - 1; i >= 0; --i) inv[i] = inv[i + 1] * (i + 1) % mod; }
证明：显然针对买最后一个fac[n]需要直接用ext_gcd求取，然后其他的fac[i]每一次其实只需要消除上一个fac[i+ 1]中的i +1的影响就可以了，所以每一次乘上i + 1即可
逆元3：O(n)递推求(1 ~ n) 在mod p意义下的逆元
/*O(n)线筛求(1 ~ n)逆元*/ inline void get_inv3(const int &n, const int &mod) { inv[1] = 1; for (register int i = 2; i <= n; ++i) inv[i] = ((-(mod / i) * inv[mod % i]) % mod + mod) % mod; }
证明：
设 令k = p / i, r = p % i, 则p = k * i + r
则 k * i + r = 0 (mod p)
两边同时乘上 r-1 * i-1,得
k * r-1+ i-1 = 0 (mod p)
移项得， i-1= -k * r-1 (mod p)
即 i-1 = -(p / i) *(p mod i)-1 (mod p)
那么我们只需要设置边界inv[1]= 1, 就可以通过递推在O(n)时间内求取 (1 ~ n) 在 mod p 意义下的逆元了
