题目:
给你两个正整数a(0 < a < 100000)和n(0 <= n <=100000000000)，计算(a^n) % b并输出结果
解析：
此题的要点在于数字a的n次方接近于无限大，导致如果直接先计算a的n次方的数值会导致结果过大而无法继续取余的运算，再次分析题意并且寻找规律，首先我们假定a=2 b=36 则依次取n(0-20)值得到以下结果:
[1, 2, 4, 8, 16, 32, 28, 20, 4, 8, 16, 32, 28, 20, 4, 8, 16, 32, 28, 20]
可以发现，[4,8,16,32,28,20]是无限重复的数列，不难得出，当n取无限大的时候，总能在结果数列中找到一个无线循环的子序列，因此得到结题思路，代码如下
#d为题中除数
def countResult(a,n,d):
#余数集合
remainArr=[]
#乘积
sum=1
while remainArr.count(sum%d)==0:
remainArr.append(sum%d)
sum=sum*a
#重复位置
repeatIndex=remainArr.index(sum%d)
#推理n处的余数
if(n>=len(remainArr)) :
index=repeatIndex+(n-repeatIndex)%(len(remainArr)-repeatIndex)
else :
index=n
#返回结果
return remainArr[index]
print(countResult(2,8,36))
| 
转播
