algorithm - 如何计算(1+a%m+a^2%m……+a^n%m)的和

Question

如何计算(1+a%m+a^2%m……+a^n%m)where的总和 m=k!, 1<=k<=12, n<=10^18。如何计算这个总和。使用电脑，时间限制为 3 秒。对不起我的错误

Answer 1

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)

Answer 2

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