kk Blog —— 通用基础

date [-d @int|str] [+%s|"+%F %T"]

逆元

https://blog.csdn.net/baidu_35643793/article/details/75268911

1.什么是逆元

当求解公式:(a/b)%m 时,因b可能会过大,会出现爆精度的情况,所以需变除法为乘法:

设c是b的逆元,则有b*c≡1(mod m);

则(a/b)%m = (a/b)1%m = (a/b)bc%m = ac(mod m);

即a/b的模等于a*b的逆元的模;

逆元就是这样应用的;

2.求逆元的方法

(1).费马小定理

在是素数的情况下,对任意整数都有。 如果无法被整除,则有。 可以在为素数的情况下求出一个数的逆元,,即为逆元。

题目中的数据范围1<=x<=109,p=1000000007,p是素数;

所以x肯定就无法被p整除啊,所以最后就得出xp-2为x的逆元啦。

复杂度O(logn);

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
const int mod = 1000000009;  
long long quickpow(long long a, long long b) {  
	if (b < 0) return 0;  
	long long ret = 1;  
	a %= mod;  
	while(b) {  
		if (b & 1) ret = (ret * a) % mod;  
		b >>= 1;  
		a = (a * a) % mod;  
	}  
	return ret;  
}  
long long inv(long long a) {  
	return quickpow(a, mod - 2);  
}  

(2)扩展欧几里得算法求逆元

可扩展欧几里得求逆元ax≡1(mod n)其中a,n互质;

复杂度:O(logn);

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
ll extend_gcd(ll a, ll b, ll &x, ll &y) {  
	if (b == 0) {  
		x = 1, y = 0;  
		return a;  
	}  
	else {  
		ll r = extend_gcd(b, a % b, y, x);  
		y -= x * (a / b);  
		return r;  
	}  
}  
ll inv(ll a, ll n) {  
	ll x, y;  
	extend_gcd(a, n, x, y);  
	x = (x % n + n) % n;  
	return x;  
}  

(3) 逆元线性筛 ( P为质数 )

求1,2,…,N关于P的逆元(P为质数)

复杂度:O(N)

代码:

1
2
3
4
5
6
const int mod = 1000000009;  
const int maxn = 10005;  
int inv[maxn];  
inv[1] = 1;  
for(int i = 2; i < 10000; i++)  
	inv[i] = inv[mod % i] * (mod - mod / i) % mod;