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 如果觉得我的文章对你有用，请随意赞赏
2 comments
《完美犯罪(经典黑白影片现代重制版 )》日本剧高清在线免费观看：https://www.jgz518.com/xingkong/154782.html
挖到了dalao的blog啊