問題描述：

? 求A^k mod B

輸入：

? 包括三個正整數A，B，k ，其中1<=A<B<=10,000 ?,1<=k<=2,000,000,000

輸出：

? 一個整數表示A^k mod B的值

樣例輸入

2 3 1

2 3 2

樣例輸出

2

1

?

?

剛開始想到的一定是，用for循環來進行累乘，然后進行計算，但是k的范圍過大，使得數據會溢出，所以不能用此方法來解題！

?

在一本書上看到的一種方法：

? ?我們可以從k的二進制進行思考，

這是求二進制數的方法，所以A^k=(A^k/2)^2;這次應該就有思路了吧

而二進制數只能是0或1，所以如果我們用二進制數來計算表示k的話，可以發現A^k <=> A*k;

#include<stdio.h> int mod(int a,int k,int b) {int temp,ans;ans=1;temp=a;while(k!=0){if(k%2==1) ans=ans*temp%b; //判斷每一次的余數是否是1，如果是1，則把我們前面算出來的temp值乘進去 temp=temp*temp%b; //每一次更新temp的值，其實也是對每一次temp的值取余，間接的減小了temp的值 k/=2;} //計算而k的進制數return ans; } int main() {int a,b,k;while(scanf("%d%d%d",&a,&b,&k)!=EOF){printf("%d\n",mod(a,k,b));}return 0; }

希望對大家有幫助

?

《新程序員》：云原生和全面數字化實踐50位技術專家共同創作，文字、視頻、音頻交互閱讀

總結

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

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