close
Content
計算 R = BP mod M
對相當大的B、P、M請寫一個有效率的演算法來。
Input
每筆測試資料有3行，各有1個整數分別代表B、P、M。
其中 0 <= B <= 2147483647 0 <= P <= 2147483647 1 <= M <= 46340
Output
輸出計算的結果，每筆測試資料一行。
Sample Input #1
3 18132 17 17 1765 3 2374859 3029382 36123
Sample Output #1
13 2 13195
python:
"""
分製法:
1.當P為偶數時
BP%M = ( (BP/2%M) * (BP/2%M) )%M
2.當P為奇數時
BP%M = ( (B1%M) * (B(P-1)/2%M) * (B(P-1)/2%M) )%M
"""
def ans(b,p,m):
#設定終止條件
if p==0:return 1
elif p==1: return b%m
#分治法
else:
if p%2==0:
half=ans(b,p//2,m)
return half*half%m
else:#p%2==1:
half=ans(b,p//2,m)
return half*half*b%m
while True:
try:
b,p,m=map(int,input().split())#跑測資的時候是一行三個數喔
print(ans(b,p,m))
except:break
文章標籤
全站熱搜
留言列表
{{ article.title }}