wordpress图纸管理网站,大连h5开发公司,wordpress重定向循环,建站一般要多少钱乘法逆元
对于缩系中的元素#xff0c;每个数a均有唯一的与之对应的乘法逆元x#xff0c;使得ax≡1(mod n) 一个数有逆元的充分必要条件是gcd(a,n)1#xff0c;此时逆元唯一存在 逆元的含义#xff1a;模n意义下#xff0c;1个数a如果有逆元x#xff0c;那么除以a相当于…乘法逆元
对于缩系中的元素每个数a均有唯一的与之对应的乘法逆元x使得ax≡1(mod n) 一个数有逆元的充分必要条件是gcd(a,n)1此时逆元唯一存在 逆元的含义模n意义下1个数a如果有逆元x那么除以a相当于乘以x。 下面给出求逆元的几种方法
1.扩展欧几里得
给定模数m求a的逆相当于求解ax1(mod m) 这个方程可以转化为ax-my1 然后套用求二元一次方程的方法用扩展欧几里得算法求得一组x0,y0和gcd 检查gcd是否为1 gcd不为1则说明逆元不存在 若为1则调整x0到0~m-1的范围中即可
PS这种算法效率较高常数较小时间复杂度为O(ln n) 2.费马小定理
在模为素数p的情况下有费马小定理 a^(p-1)1mod p 那么a^(p-2)a^-1(mod p) 也就是说a的逆元为a^(p-2)
而在模不为素数p的情况下有欧拉定理 a^phi(m)1mod m (a⊥m) 同理a^-1a^(phi(m)-1)
因此逆元x便可以套用快速幂求得了xa^(phi(m)-1)
但是似乎还有个问题如何判断a是否有逆元呢?
检验逆元的性质看求出的幂值x与a相乘是否为1即可
PS:这种算法复杂度为Olog2N在几次测试中常数似乎较上种方法大
当p比较大的时候需要用快速幂求解 当模p不是素数的时候需要用到欧拉定理
a^phi(p)≡1 (mod p)
a*a^(phi(p)-1)≡1 (mod p)
a^(-1)≡a^(phi(p)-1) (mod p)
所以 时间复杂度即求出单个欧拉函数的值
(当p为素数的时候phi(p)p-1,则phi(p)-1p-2可以看出欧拉定理是费马小定理的推广)
PS这里就贴出欧拉定理的板子很少会用欧拉定理求逆元 3.特殊情况
一
当N是质数 这点也很好理解。当N是质数0 a N时则a肯定存在逆元。 而解出的就满足故它是a的逆元。
在CF 696C
求解就灰常方便了…
二
求逆元一般公式(条件b|a)
ansa/bmodmamod(mb)/b
公式证明 PS:实际上a mod (bm)/b这种的对于所有的都适用不区分互不互素,而费马小定理和扩展欧几里得算法求逆元是有局限性的它们都会要求与互素如果a与m不互素那就没有逆元这个时候需要a mod (bm)/b来搞此时就不是逆元的概念了。但是当a与m互素的时候bm可能会很大不适合套这个一般公式所以大部分时候还是用逆元来搞
4.逆元打表 有时会遇到这样一种问题在模质数p下求1~n逆元 n p这里为奇质数。可以O(n)求出所有逆元有一个递推式如下 它的推导过程如下设那么 对上式两边同时除进一步得到 再把和替换掉最终得到 初始化这样就可以通过递推法求出1-n模奇素数的所有逆元了。 另外有个结论模的所有逆元值对应中所有的数比如那么对应的逆元是。
typedef long long ll;
const int N 1e5 5;
int inv[N];void inverse(int n, int p) {inv[1] 1;for (int i2; in; i) {inv[i] (ll) (p - p / i) * inv[p%i] % p;}
}转自https://blog.csdn.net/guhaiteng/article/details/52123385更多例题https://blog.csdn.net/acdreamers/article/details/8220787 线性求逆元 题目
ll c(int r,int l) {if (rl) return 0;return jie[r]*inv[l]%mod*inv[r-l]%mod;
}
int main()
{jie[1] 1;jie[0] 1;inv[1] 1;inv[0] 1;for(int i 2; iMAX-1; i) jie[i] (jie[i-1] * i)%mod;for(int i 2; iMAX-1; i) {inv[i] (mod - mod/i*inv[mod%i]%mod)%mod;}
//这两个求逆元的公式都可以使用
// for (int i2; iMAX; i) {
// inv[i]inv[mod%i]*(mod-mod/i)%mod;
// }
//预处理逆元的前缀积for (int i2; iMAX; i) inv[i]inv[i-1]*inv[i]% mod;
线性求逆元 题目
const ll mod 10000000007;
const ll N 3000005;
const ll M 3e53;
int n;
ll fac[1000005]; //阶乘
ll inv_of_fac[1000005]; //阶乘的逆元
int a[15];
ll dp[150][12];
ll qpow(ll x,ll n)
{ll ret1;for(; n; n1){if(n1) retret*x%mod;xx*x%mod;}return ret;
}
void init()
{fac[1]1;for(int i2; iM; i)fac[i]fac[i-1]*i%mod;inv_of_fac[M]qpow(fac[M],mod-2);for(int iM-1; i0; i--)inv_of_fac[i]inv_of_fac[i1]*(i1)%mod;//inv_of_fac[i]qpow(fac[i],mod-2);//为什么不行啊 //也行
}
ll C(ll a,ll b)
{if(ba) return 0;if(b0) return 1;return fac[a]*inv_of_fac[b]%mod*inv_of_fac[a-b]%mod;
}咖啡鸡的求逆元
#includebits/stdc.h
using namespace std;
const int maxn4005;
const int E2000;
typedef long long ll;
const ll M1000000007;
ll f[maxn],nf[maxn],inv[maxn],dp[2][maxn];
int n,m;
ll C(ll x,ll y){return f[x]*nf[y]%M*nf[x-y]%M;
}
ll K(ll x){return C(x*2,x)*inv[x1]%M;
}
void add(ll x,ll y){xy; if (xM) x-M;
}
int main(){inv[1]1; for (int i2;imaxn;i) inv[i]M-(M/i)*inv[M%i]%M;f[0]nf[0]1; for (int i1;imaxn;i) f[i]f[i-1]*i%M,nf[i]nf[i-1]*inv[i]%M;return 0;
}
