你不可错过的快速幂算法模板超详细整理

我不是女神ヾ 2021-07-25 01:01 425阅读 0赞

### 快速幂算法 ###

*   *   *  1.介绍
         *  2.模板
         *  3.优化
         *  4.终极优化
         *  5.例题
         *  6.快速幂求逆元

### 1.介绍 ###

快速幂算法能帮我们算出指数非常大的幂，传统的求幂算法之所以时间复杂度非常高（为O(指数n)），就是因为当指数n非常大的时候，需要执行的循环操作次数也非常大。所以我们快速幂算法的核心思想就是每一步都把指数分成两半，而相应的底数做平方运算。这样不仅能把非常大的指数给不断变小，所需要执行的循环次数也变小，而最后表示的结果却一直不会变。

### 2.模板 ###

快速幂算模板
    long long fastPower(long base, long long power)
    { 
    	long long result = 1;
    	while (power > 0)
    	{ 
    		if (power % 2 == 0)//如果指数为偶数
    		{ 
    			power = power / 2;  //把指数缩小一半
    			base = base * base;  //底数变大为原来的平方
    		}
    		else  //如果指数为奇数
    		{ 
    			power = power - 1;  // 把指数减去1，使其变成一个偶数
    			result = result * base; //此时记得要把指数为奇数时分离出来的底数的一次方收集好
    			power = power / 2;  //此时指数为偶数，可以继续执行指数减半操作
    			base = base * base;  //底数变大为原来的平方
    		}
    	}
    	return result;
    }

### 3.优化 ###

long long fastPower(long long base, long long power) { 
        long long result = 1;
        while (power > 0) { 
            if (power % 2 == 1) { 
                result = result * base ;
            }
            power = power / 2;
            base = base * base;
        }
        return result;
    }

### 4.终极优化 ###

long long fastPower(long long base, long long power)
    { 
    	long long result = 1;
    	while (power > 0)
    	{ 
    		if (power & 1)  //此处等价于power%2==1 
    		{ 
    			result = result * base;
    		}
    		power >>= 1; //此处等价于power=power/2; 指数减半
    		base = base * base;  //底数平方
    	}
    	return result;
    }

### 5.例题 ###

(1) 题目

求 a 的 b 次方对 p 取模的值。  
**输入格式**  
三个整数 a,b,p ,在同一行用空格隔开。  
**输出格式**  
输出一个整数，表示a^b mod p的值。  
数据范围  
0≤a,b,p≤109  
数据保证 p≠0  
**输入样例：**  
3 2 7  
**输出样例：**  
2

(2) 代码

#include<iostream>
    #include<cstdio>
    using namespace std;
    long long fastPower(long long base, long long power,long long p)
    { 
    	long long result = 1%p;
    	while (power > 0)
    	{ 
    		if (power & 1)
    		{ 
    			result = result * base % p;
    		}
    		power >>= 1;
    		base = base * base % p;
    	}
    	return result;
    }
    int main()
    { 
    	int a, b, p;
    	cin >> a >> b >> p; 
    	cout << fastPower(a, b, p) << endl;
    	return 0;
    }

### 6.快速幂求逆元 ###

**1.乘法逆元**  
乘法逆元的定义  
若整数b，m互质，并且对于任意的整数 a，如果满足b|a，则存在一个整数x，使得a/b≡a∗x(mod m)，则称x为b的模m乘法逆元，记为b^−1(mod m)。  
b存在乘法逆元的充要条件是b与模数m互质。当模数m为质数时，b^m−2即为b的乘法逆元。  
**当n为质数时，可以用快速幂求逆元：**  
a / b ≡ a \* x (mod n)  
两边同乘b可得 a ≡ a \* b \* x (mod n)  
即 1 ≡ b \* x (mod n)  
同 b \* x ≡ 1 (mod n)  
由费马小定理可知，当n为质数时  
b ^ (n - 1) ≡ 1 (mod n)  
拆一个b出来可得 b \* b ^ (n - 2) ≡ 1 (mod n)  
故当n为质数时，b的乘法逆元 x = b ^ (n - 2)  
**当n不是质数时，可以用扩展欧几里得算法求逆元：**  
a有逆元的充要条件是a与p互质，所以gcd(a, p) = 1  
假设a的逆元为x，那么有a \* x ≡ 1 (mod p)  
等价：ax + py = 1  
exgcd(a, p, x, y)  
**2.题目练习**  
给定n组ai,pi，其中pi是质数,求ai模pi的乘法逆元，若逆元不存在则输出impossible。  
注意：请返回在0∼p−1之间的逆元。  
乘法逆元的定义  
若整数b，m互质，并且对于任意的整数 a，如果满足b|a，则存在一个整数x，使得a/b≡a∗x(mod m)，则称x为b的模m乘法逆元，记为b^−1(mod m)。  
b存在乘法逆元的充要条件是b与模数m互质。当模数m为质数时，b^m−2即为b的乘法逆元。  
**输入格式**  
第一行包含整数n。  
接下来n行，每行包含一个数组ai,pi，数据保证pi是质数。  
**输出格式**  
输出共n行，每组数据输出一个结果，每个结果占一行。  
若ai模pi的乘法逆元存在，则输出一个整数，表示逆元，否则输出impossible。  
**数据范围**  
1≤n≤105,  
1≤ai,pi≤2∗109  
**输入样例：**  
3  
4 3  
8 5  
6 3  
**输出样例：**  
1  
2  
impossible  
代码

#include<iostream>
    #include<cstdio>
    using namespace std;
    typedef long long ll;
    ll qmi(ll a, ll p, ll mod)
    { 
    	ll ans = 1;
    	while (p)
    	{ 
    		if (p & 1) ans = ans * a%mod;
    		p >>= 1;
    		a = a * a%mod;
    	}
    	return ans;
    }
    int main()
    { 
    	int n;
    	cin >> n;
    	while (n--)
    	{ 
    		int a, p;
    		cin >> a >> p;
    		if (a%p) cout << qmi(a, p - 2, p) << endl;   //如果a%p==0，则a^p-2%p==0,a不会有逆元
    		else cout << "impossible" << endl;
    	}
    	return 0; 
    }