如何計算總和（1 + a％m + a^2％m ...... + a^n％m）

Question

如何計算總和(1+a%m+a^2%m……+a^n%m)其中 m=k!, 1<=k<=12, n<=10^18。如何計算這個總和。 使用電腦和時間限制是3秒。 對不起我的錯

Answer 1

sum = 0; 
i = 0; 
while(i <= n){ 
sum = sum + math.pow(a,i); 
i++; 
} 
result = sum % m; 

Answer 2

1+a+a^2+...+a^n = (1+a+a^2+...+a^n)*(1-a)/(1-a) = 
= (1 - a^(n+1))/(1-a) 

換句話說，你的表情可以被計算爲：

(1 - a^(n+1))/(1-a) % m 

或者，在方案的形式，

fmod((1-pow(a,n+1))/(1-a), m)