OI Wiki了解一下


最大公约数

int gcd(int a, int b){
    if(b == 0) return a;
    return gcd(b, a % b);
}

裴蜀定理(贝祖定理)

  • 设$a,b$是不全为零的整数,则存在整数$x,y$, 使得$ax+by=gcd(a,b)$.

扩展欧几里得

  • 用于求解方程$ax+by=gcd(a,b)$
  • 代码:
    int exgcd(int a, int b, int &x, int &y){
    if(b == 0){
        y = 0, x = 1;
        return a;
    }
    int r = exgcd(b, a % b, y, x);
    y -= a / b * x;
    return r;
    }

乘法逆元

如果一个线性同余方程$ax\equiv 1(mod\ b)$,则$x$称为$a\mod b$的逆元,记作$a^{-1}$。

求解a的逆元

扩展欧几里得法

  • 扩展欧几里得法和求解线性同余方程是一个原理,在这里不展开解释。

    快速幂法

  • 因为$ax\equiv 1(mod\ b)$

    所以$ax\equiv a^{b-1}(mod\ b)$

    所以$x\equiv a^{b-2}(mod\ b)$

然后就可以用快速幂求了

线性求任意n个数的逆元

首先计算$n$个数的前缀积$s_i$,然后用快速幂法求$s_n$的逆元,记为$sv_n$。

因为$sv_n$是前$n$个数的积的逆元,所以这个数乘$a_i$,会和其逆元抵消,于是就得到了$a_1$到$a_{n-1}$的积逆元,记为$sv_{n-1}$。

然后就能计算出所有$sv_i$,$a_i$的逆元就可以由$s_{i-1}\times sv_i$求得。

时间复杂度:$O(n+log\ p)$

s[0] = 1;
for (int i = 1; i <= n; ++i) s[i] = s[i - 1] * a[i] % p;
sv[n] = qpow(s[n], p - 2);
// 当然这里也可以用 exgcd 来求逆元,视个人喜好而定.
for (int i = n; i >= 1; --i) sv[i - 1] = sv[i] * a[i] % p;
for (int i = 1; i <= n; ++i) inv[i] = sv[i] * s[i - 1] % p;

P.S.刚刚我做了两道例题,现在感觉。。。脑子一片浆糊。

Last modification:March 8th, 2020 at 05:15 pm