題目描述

輸入b，p，k的值，求b^p mod k的值。其中b，p，k*k為長整型數。

輸入輸出格式

輸入格式：

三個整數b,p,k.

輸出格式：

輸出“b^p mod k=s”

s為運算結果

思路：

顯然取余和乘法誰都會

關鍵在于快速

我們知道乘方有一個性質

x^n=(x^2)^（n/2）

這樣我們就能通過二分使時間復雜度降到log級別

你可能會說，n%2==1怎么辦？？

和簡單，再定義一個變量作為暫存器，乘一下x

這時候又有另一個定理

x^n=x^(n-1)*x

所以n可以減一

最后將暫存器和x乘起來即可

代碼：

#include<iostream>
#include<cstdio>
using namespace std;
int  a,b,s;
int res=1;
int pw(int j,int k)
{if(k==0){res=res%s;return res;}j=j%s;if(k%2==1){res=res*j;res=res%s;k--;pw(j,k);}else{k=k/2;j=j*j;pw(j,k);}    
}
int main()
{cin>>a>>b>>s;long long x=1;x=pw(a,b);cout<<a<<"^"<<b<<" mod "<<s<<"="<<x;
}

?

轉載于:https://www.cnblogs.com/ztz11/p/8973023.html

總結

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

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