Logo

菜单

Akvicor
Akvicor
发布于 2019-08-01 / 72 阅读
0
0

逆元的求法（欧拉定理、阶乘逆元、费马小定理、模质数p的情况）

乘法逆元

对于缩系中的元素，每个数a均有唯一的与之对应的乘法逆元x，使得，一个数有逆元的充分必要条件是gcd(a,n)=1，此时逆元唯一存在

在一般数学中，我们所说的逆元就是倒数，但是在数论中，如果一个数字a存在一个对p的逆元x，就可以写成的形式(此处p与a互质，若不互质，则不存在逆元)

逆元的含义：模n意义下，1个数a如果有逆元x，那么除以a相当于乘以x。

满足的值就是关于的乘法逆元

当我们要求的值时，我们就可以用到乘法逆元。我们可以用过求b关于p的乘法逆元k，将a乘上k再模p，即。其结果与等价

证明

根据有

把k带入得

所以原式等于：

拓展欧几里得

拓展欧几里得:的解一定存在

当我们要求关于的逆元时，若逆元存在，则。假设逆元为，即：

我们可以展开一下变成，由于可正可负，我们可以得到，其实就是。

我们用拓展欧几里得求出一个最小的x就是关于的一个逆元。

这个方程可以转化为，然后套用求二元一次方程的方法，用拓展欧几里得算法求得一组和gcd，检查gcd是否为1，gcd不为1则说明逆元不存在，若为1，则调整到的范围中即可

求解：

现在我们已经有了了。我们想试着求出一个特解。

根据欧几里得算法我们可以知道。

而且我们可以看出

由此我们可得：(由于两边,值不用，我们用和进行区分)

我们想要把式子简化一下，可以从入手，即。

所以我们可以化简得到

移项：

系数相等，所以我们可以解得

根据欧几里得算法，我们一直递归下去，总会到

所以式子变成了。此时我们取一个特解。然后往回推，就可以得到一开始的那个x。

此时解出来的就是关于的一个逆元。

PS：算法效率较高，常数较小，时间复杂度

void exgcd(LL a, LL b, LL &x, LL &y) {
	if (b == 0) {
		x = 1;y = 0;
	} else {
		exgcd(b, a%b, y, x);
		y -= (a/b) * x;
	}
}

void extgcd(LL a, LL b, LL &d, LL &x, LL &y) {
    if (!b) {
        d = a;        
        x = 1;
        y = 0;
    } else {
        extgcd(b, a % b, d, y, x);
        y -= x * (a / b);
    }
}

LL inverse(LL a, LL n) {
    LL d, x, y;
    extgcd(a, n, d, x, y);
    return d == 1 ? (x + n) % n : -1;
}

递推求阶乘逆元

我们经常会用到阶乘的逆元，我们可以考虑用费马小定理先求出最大的那个阶乘的逆元，然后再往回推

我们可以把的逆元表示为。

我们要求的逆元，我们可以考虑给乘上一个把他变为。

即

因此是关于的一个逆元。

void init() {
	fact[0] = 1;
	for (int i = 1; i < maxn; i++) {
		fact[i] = fact[i - 1] * i %mod;
	}
	inv[maxn - 1] = power(fact[maxn - 1], mod - 2);
	for (int i = maxn - 2; i >= 0; i--) {
		inv[i] = inv[i + 1] * (i + 1) %mod;
	}
}

费马小定理

在模为素数p的情况下，有费马小定理，（左右同除a）得，也就是说a的逆元为

符号解释

既约，，a与m既约、不可约、互素：

既约，或称不可约，或称互质，或称互素，a,m既约，记做或即a,m二者的最大公约数为1，已经约去公因子到不可再约了。

而在模数不为素数p得情况下，有欧拉定理

同理

因此逆元x便可以套用快速幂求得了

如何判断a是否有逆元？检验逆元的性质，看求出的幂值x与a相乘是否为1即可

PS：这种算法复杂度为在几次测试中，常数似乎较上种方法大

当p比较大的时候需要用快速幂求解

LL pow_mod(LL x, LL n, LL mod) {
    LL res = 1;
    while (n > 0) {
        if (n & 1)res = res * x % mod;
        x = x * x % mod;
        n >>= 1;
    }
    return res;
}

当模p不是素数的时候需要用到欧拉定理

所以时间复杂度即求出单个欧拉函数的值

(当p为素数的时候，则可以看出欧拉定理是费马小定理的推广)

PS：这里就贴出欧拉定理的板子，很少会用欧拉定理求逆元

特殊情况

一

当N是质数，这点也很好理解。当N是质数，时，则a肯定存在逆元。而解出的就满足，故它是a的逆元。

CF 696C

二

求逆元一般公式(条件b|a)

证明：

PS：实际上这种对于所有的都适用，不区分互补互素，而费马小定理和拓展欧几里得算法求逆元是有局限性的，它们都会要求a与m互素，如果a与m不互素，那就没有逆元，这个时候需要来搞（此时就不是逆元的概念了）。但是当a与m互素的时候，bm可能会很大，不适合套这个一般公式，所以大部分时候还是用逆元来搞

通过递推求1~n的逆元

有时候会遇到这样一种问题，在模质数p下，求逆元（这里p为奇质数）。可以O(n)求出所有逆元，有一个递推式如下

推导过程如下，设

左右同时除，得到

再把t和k替换掉

初始化，这样就可以通过递推法求出1->n模奇素数p的所有逆元了

另外有个结论 1->p 模 p的所有逆元值对应 1->p 中所有的数，比如p=7，那么 1->6 对应的逆元是 1 4 5 2 3 6

const int N = 1e5 + 5;
int inv[N];

void inverse(int n, int p) {
    inv[1] = 1;
    for (int i = 2; i <= n; ++i) {
        inv[i] = (ll) (p - p / i) * inv[p % i] % p;
    }
}

通过递推求n!的逆元

递推公式：

// 快速幂求逆元
int quick_inverse(int n, int p) {
	int ret = 1;
	int exponent = p - 2;
	for (int i = exponent; i; i >>= 1, n = n * n % p) {
		if (i & 1) {
			ret = ret * n % p;
		}
	} 
	return ret;
}
int invf[N], factor[N];
void get_factorial_inverse(int n, int p) {
	factor[0] = 1;
	for (int i = 1; i <= n; ++i) {
		factor[i] = i * factor[i - 1] % p;
	}
	invf[n] = quick_inverse(factor[n], p);
	for (int i = n-1; i >= 0; --i) {
		invf[i] = invf[i + 1] * (i + 1) % p;
	}
}

题目

POJ-1845

网络流
莫比乌斯反演

评论