如何计算(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

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)