快速冪求模

輸入a，b，c，求a的b次方對c的模，如果直接用pow函數(shù)，時間復雜度為o(n),有可能會發(fā)生超時或者超過long long的取值范圍

或每次運算都對ans取余，但這樣只能優(yōu)化取值范圍，所以要用到快速冪求模，利用二分的思想，減少相乘次數(shù)，增大相乘的數(shù)值

#include<iostream> #include<cstdio> using namespace std; typedef long long ll; ll pow(ll a, ll b, ll c) {ll ans = 1;a %= c;while(b) {if(b & 1) ans = ans * a % c;b /= 2;a = a * a % c;}return ans; } int main() {int n;ll a, b, c;cin >> n;while(n--) {cin >> a >> b >> c;int ji = 1;cout << pow(a, b, c) << endl; }return 0; }

轉載于:https://www.cnblogs.com/kindleheart/p/8749245.html

總結

以上是生活随笔為你收集整理的快速幂求模的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內容還不錯，歡迎將生活随笔推薦給好友。