Loading... OI Wiki了解一下 --- ## 最大公约数 ```cpp 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)$ - 代码: ```cpp 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)$ ```cpp 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 8, 2020 © Allow specification reprint Like 如果觉得我的文章对你有用,请随意赞赏
One comment
挖到了dalao的blog啊