大数的快速幂模运算,快速幂运算

文章目录 前言一、快速幂（Fast Exponentiation）的定义：二、快速幂原理：三、常规求幂：四、简单快速求幂：四、递归快速求幂：五、位运算快速求幂：六、高精度快速求幂：六、python高精度快速求幂：七、实战演习：总结

前言

本文讲述快速幂的原理，以及用法

一、快速幂（Fast Exponentiation）的定义：

定义：快速求，取base为底数的exp次幂，即求：baseexp；

时间复杂度： O(log₂N)

二、快速幂原理：

思想：每一步都把指数分成两半，而相应的底数做平方运算。不仅能把非常大的指数给不断变小，所需要执行的循环次数也变小，而最后表示的结果却一直不会变。

原理：(a* b) % m = ((a % m) * (b % m)) % m

三、常规求幂：

代码块：

#include <bits/stdc++.h>using namespace std;typedef long long ll;ll Pow1(ll my_base, ll my_exp) {ll ans = 1;for (int i = 1; i <= my_exp; i++) ans *= my_base;return ans;}int main() {ios::sync_with_stdio(false);cin.tie(0); //断开同步流 ll my_base, my_exp, result;clock_t my_start, my_end;cin >> my_base >> my_exp;my_start = clock();//该函数返回值是硬件滴答数result = Pow1(my_base, my_exp);cout << my_base << "^" << my_exp << "=" << result << endl;my_end = clock();cout << "time=" << ((double)my_end - my_start) / CLK_TCK << "s" << endl;//要换算成秒，需要除以CLK_TCK或者 CLK_TCKCLOCKS_PER_SECreturn 0;}

运行结果：

四、简单快速求幂：

代码块：

#include <bits/stdc++.h>using namespace std;typedef long long ll;ll Pow2(ll x, ll y) {ll ans = 1, base = x;while (y != 0) {if (y % 2 != 0) ans *= base;base *= base;y /= 2;}return ans;}int main() {ios::sync_with_stdio(false);cin.tie(0); //断开同步流 ll my_base, my_exp, result;clock_t my_start, my_end;cin >> my_base >> my_exp;my_start = clock();//该函数返回值是硬件滴答数result = Pow2(my_base, my_exp);cout << my_base << "^" << my_exp << "=" << result << endl;my_end = clock();cout << "time=" << ((double)my_end - my_start) / CLK_TCK << "s" << endl;//要换算成秒，需要除以CLK_TCK或者 CLK_TCKCLOCKS_PER_SECreturn 0;}

运行结果：

四、递归快速求幂：

代码块：

#include <bits/stdc++.h>using namespace std;typedef long long ll;ll Pow3(ll my_base, ll my_exp) {if (my_exp == 1)return my_base;ll ans = Pow3(my_base, my_exp / 2);return (my_exp % 2 == 0 ? 1 : my_base) * ans * ans;}int main() {ios::sync_with_stdio(false);cin.tie(0); //断开同步流 ll my_base, my_exp, result;clock_t my_start, my_end;cin >> my_base >> my_exp;my_start = clock();//该函数返回值是硬件滴答数result = Pow3(my_base, my_exp);cout << my_base << "^" << my_exp << "=" << result << endl;my_end = clock();cout << "time=" << ((double)my_end - my_start) / CLK_TCK << "s" << endl;//要换算成秒，需要除以CLK_TCK或者 CLK_TCKCLOCKS_PER_SECreturn 0;}

运行结果：

五、位运算快速求幂：

代码块：

#include <bits/stdc++.h>using namespace std;typedef long long ll;ll Pow3(ll my_base, ll my_exp) {int ans = 1, base = my_base;while (my_exp != 0) {if (my_exp & 1 != 0){//逐位获取b的二进制位，遇0累乘ans *= base;}base *= base;my_exp >>= 1;}return ans;}int main() {ios::sync_with_stdio(false);cin.tie(0); //断开同步流 ll my_base, my_exp, result;clock_t my_start, my_end;cin >> my_base >> my_exp;my_start = clock();//该函数返回值是硬件滴答数result = Pow3(my_base, my_exp);cout << my_base << "^" << my_exp << "=" << result << endl;my_end = clock();cout << "time=" << ((double)my_end - my_start) / CLK_TCK << "s" << endl;//要换算成秒，需要除以CLK_TCK或者 CLK_TCKCLOCKS_PER_SECreturn 0;}

运行结果：

六、高精度快速求幂：

代码块：

#include <bits/stdc++.h>using namespace std;typedef long long ll;const ll mod = 1e7; //自定义取模的数据,视数据大小的情况而定//a ^ bll ksm(ll a, ll b, ll mod) { //time_complex=O(logn)ll ans = 1, base = a;while (b != 0) {if ((b & 1) != 0) { //“b & 1”指取b的二进制数的最末位ans = (ans * base) % mod; //累乘，以便随时对ans做出贡献。}base = (base * base) % mod;b >>= 1; //右移1位，删去最低位。}return ans;}int main() {ios::sync_with_stdio(false);cin.tie(0); //断开同步流 ll a, b, result;clock_t my_start, my_end;cin >> a >> b;my_start = clock();//该函数返回值是硬件滴答数result = ksm(a, b, mod); cout << a << "^" << b << "=" << result << endl;my_end = clock();cout << "time=" << ((double)my_end - my_start) / CLK_TCK << "s" << endl;//要换算成秒，需要除以CLK_TCK或者 CLK_TCKCLOCKS_PER_SECreturn 0;}

运行结果：

六、python高精度快速求幂：

代码块：

a, b = map(int, input().split())mod = 10000000result = pow(a, b, mod)print("{0}^{1}={2}".format(a, b, result))

运行结果：

七、实战演习：

题目来源：
https://ac.nowcoder.com/acm/problem/213988

程序代码：
第一种写法：

#include<bits/stdc++.h>using namespace std;typedef long long ll;/*long long qmod(ll a,ll b,int c){ if(b==1) return a; if(b&1) return a*qmod(a,b-1,c)%c; else { ll m=qmod(a,b/2,c); return m*m%c; } } *///用二分还是超时ll qmod(ll a,ll b,ll c)//快速幂{ int r=1; while(b) { if(b&1) r=a*r%c; a=a*a%c; b>>=1; //b的二进制形式删除最后一位 } return r;}int main(){ long long a,b,c; c=998244353; cin>>a>>b; if(a>c) a=a%c; else { ll ans=qmod(b+1,a,c); cout<<ans<<endl; } }

第二种写法：

n, m = map(int, input().split())sum = pow(m+1,n,998244353)print(sum)

运行结果：

总结

本文讲述快速幂的基本用法。

如有错误，敬请指教！