费马小定理
假如 p 是质数, 且 gcd(a,p)=1(a 和 p 互质), 那么 a^(p-1) ≡ 1(mod p), 即 ( a^(p-1) )%p = 1.
可以用这个定理快速求得一个大数的余数. 例如:
- \(欲求: 2^{
- 100
- }\ \%\ 13=\ ?\)
- \(因为 2 与 13 互质, 故根据费马小定理有: 2^{
- 13-1
- }\equiv1(mod\ 13)\)
- \(即: 2^{
- 12
- }\ \%\ 13 = 1\)
- \(又: 2^{
- 100
- }=(2^{
- 12
- })^{
- 8
- }*2^4\)
- \(所以, 2^{
- 100
- }\ \%\ 13=(2^{
- 12
- })^{
- 8
- }*2^4\ \%\ 13=((2^{
- 12
- })^{
- 8
- }\ \%\ 13)*(2^4\ \%\ 13)\ \%\ 13=((2^{
- 12
- }\ \%\ 13)^8\ \%\ 13)*(3)\ \%\ 13=3\)
求逆元(通过快速幂使得复杂度在 \(O(log)\)):
- inv(LL a, LL p) { //a 关于 p 的逆元
- return qpow(a, p-2, p);
- }
关于逆元的求法还有公式变形法 (递归, 递推) 以及拓展欧几里得算法(证明是将二项的不定方程分别 mod A 以及 mod B 化简)
关于求逆元公式法的证明:
设 x = p % a,y = p / a
则 x + y * a = p
(x + y * a) % p = 0
移项 x % p = (-y) * a % p
- x * inv(a) % p = (-y) % p
- inv(a) = (p - y) * inv(x) % p
所以 inv(a) = (p - p / a) * inv(p % a) % p
部分代码实现:
- #include <iostream>
- using namespace std;
- typedef long long LL;
- LL exgcd(LL A, LL B, LL &x, LL &y) {
- if (B == 0) {
- x = 1;
- y = 0;
- return A;
- }
- LL gcdnum = exgcd(B, A % B, x, y);
- LL tmp = y;
- y = x - A/B*y; // 算上来的 x,y 计算出新的 x,y
- x = tmp;
- return gcdnum;
- }
- LL qmul(LL a, LL b, LL mod) {
- LL ans = 0;
- a %= mod;
- while (b) {
- if (b&1) {
- ans = (ans + a) % mod;
- }
- a = (a <<1) % mod;
- b>>= 1;
- }
- return ans;
- }
- LL qpow(LL a, LL b, LL mod) {
- LL ans = 1;
- a %= mod;
- while (b) {
- if (b & 1) {
- ans = qmul(ans, a, mod);
- }
- a = qmul(a, a, mod);
- b>>= 1;
- }
- return ans;
- }
- // 法一: 费马小定理
- LL inv_1(LL a, LL p) { //a 关于 p 的逆元
- return qpow(a, p-2, p);
- }
- // 法二: 拓展欧几里得
- LL inv_2(LL a, LL p) {
- LL x, y;
- if (exgcd(a, p, x, y) != 1) return -1; // 不满足 a p 互质
- return (x % p + p) % p; // 变为正的
- }
- // 法三
- LL inv_3(LL a, LL p) {
- // 求 a 关于 p 的逆元, 注意: a 要小于 p, 最好传参前先把 a%p 一下
- return a == 1 ? 1 : (p - p / a) * inv_3(p % a, p) % p;
- }
- const int maxn = (int)2e5 + 5;
- const int MOD = (int)1e9 + 7;
- int inv[maxn];
- void inv_4(){ // 法三递推版 O(n)
- inv[1] = 1;
- for(int i = 2; i < maxn; i ++){
- inv[i] = (MOD - MOD / i) * 1ll * inv[MOD % i] % MOD;
- }
- }
- int main() {
- cout << "inv_1 :" << inv_1(100, MOD) << endl;
- cout << "inv_2 :" << inv_2(100, MOD) << endl;
- cout << "inv_3 :" << inv_3(100, MOD) << endl;
- inv_4();
- cout << "inv_4 :" << inv[100] << endl;
- return 0;
- }
费马小定理
来源: http://www.bubuko.com/infodetail-3038114.html