【数论】【倍增】等比数列求和

题目大意:给定$n,l,r$求$\sum_{i=l}^rn^i$其中$2<=n<=10^9;1<=l,r<=10^{18}$

总之就是求和公式不可用问题

  1. 提公因式$n^l$,原式变为$n^l\sum_{i=0}^{r-l}n^i$
  2. $log_2l$求出$n^l$
  3. 方便起见,我们定义自然数集上的函数$f(i)=f^2(i-1),f(0)=1,f(1)=n$以及$h(i)=h(i-1)(f(i)+1),h(0)=1$,定义变量$len=r-l+1$
  4. 对于$\sum_{i=0}^{len-1}n^i$,我们隔一个数提一次公因式,得到$(n+1)\sum_{i=0}^{\lfloor\frac{len-1}{2}\rfloor}n^{2i}$
  5. 以此类推,我们得到$len=2^k$时,$\sum_{i=0}^{len-1}n^i=\prod_{i=1}^{k}h(i)$
  6. 特殊地,当$len=1$时,有$\sum_{i=0}^{len-1}n^i=1$显然成立
  7. 我们通过画图发现,求和得到的$ans$其实与$len$的二进制位相关
  8. 通过更进一步观察,我们得到如下结论:$ans$需要进行一次求和,当且仅当$len$二进制位当前位为$1$
  9. 再结合之前提公因式得到的结论,我们得到$ans$在$len$倒数第$k$位为$1$时需要同$h(k-1)·f(k)^{\lfloor\frac{len}{2^{k-1}}\rfloor-1}$求和
  10. 对于$f(x)$与$h(x)$我们可以在$O(60)$的复杂度内完成预处理
  11. 于是我们就得到了这份时间复杂度最差为$O(3600)$的代码
void solve2(){
    n%=MOD;
    a[0]=b[0]=1;
    a[1]=n;
    for(int i=2;i<=60;++i) a[i]=a[i-1]*a[i-1]%MOD;
    for(int i=1;i<=60;++i) b[i]=b[i-1]*(a[i]+1)%MOD;
    long long ans=0,w=n,pw=1;
    r=r-l+1;
    while(l){
        if(l&1) pw=pw*w%MOD;
        l>>=1,w=w*w%MOD;
    }int t=0;
    while(r){
        if(r&1){
            long long y=r-1,q=1;w=a[t+1];
            while(y){
                if(y&1) q=q*w%MOD;
                y>>=1,w=w*w%MOD;
            }ans=(ans+q*b[t])%MOD;
        }r>>=1,++t;
    }printf("%lld\n",ans*pw%MOD);
}