逆元

1.费马小定理解（借助快速幂）

单次计算的复杂度即为快速幂的复杂度 $O(logX)$。限制：$mod$必须是质数，且需要满足$x$与$mod$互质

ll inv(ll x){return qpow(x,mod-2,mod);}

2.扩展欧几里得解

此方法的$lmod$没有限制，复杂度为$O(logx)$，但是比快速幂法常数大一些

using LL = long long;

// 求解 ax + by = gcd(a, b)，返回 gcd(a, b)
ll exgcd(ll a, ll b, ll &x, ll &y) {
    if (!b) { x = 1; y = 0; return a; }
    ll d = exgcd(b, a % b, y, x);
    y -= a / b * x;
    return d;
}

// 求 a 在 mod 下的乘法逆元，不存在则返回 -1
ll getInv(ll a, ll mod) {
    ll x, y;
    ll d = exgcd(a, mod, x, y);
    return d == 1 ? (x % mod + mod) % mod : -1;
}

离线求解：线性递推解

以$O(N)$的复杂度完成$1-N$中全部逆元的计算

inv[1] = 1;
for (int i = 2; i <= n; i ++ )
    inv[i] = (p - p / i) * inv[p % i] % p;
·``