约数之和那里的等比数列求和p^0+p^1+...+p^k(最后结果modM)的求法分析(为了简便表示，并没有将计算过程中的取模都写出来)

(1)秦九邵算法：

int t=0;
k=k+1;//这样k才能表示p的指数
while(k--)t=(t*p+1)%M;

简单解释，一开始t=0==>t=tp+1=1==>t=tp+1=p+1==>t=t*p+1=p^2+p+1==>…
复杂度为O(k)

(2)视频中提到的快速幂：更加适合求个项，比如求p^k，求一项的复杂度为O(logk),那么等比求和的话k项之和的复杂度就是O(log1+log2+......+logk)=O(log(k!))，相比(1)，适用度不高(就求等比数列之和而言)

快速幂模板

int qmi(int a,int b,int p)
{
    int res=1%p;
    while(b)
    {
        if(b&1)res=(ll)res*a%p;
        b>>=1;
        a=(ll)a*a%p;
    }

    return res;
}

(3)基于分治实现O(logk)的求和方法：

首先定义sum(p,k)=p^0+p^1+...+p^k

如果说sum(p,k)有偶数项，那么k为奇数，k=k/2+(k/2+1)

那么sum(p,k)=p^0+p^1+...+p^k
                     =(p^0+p^1+...+p^(k/2))+(p^(k/2+1)+...+p^k)
                     =(p^0+p^1+...+p^(k/2))+p^(k/2+1)*(p^0+p^1+...+p^(k/2))
                     =(1+p^(k/2+1))*sum(p,k/2)//这里的`p^(k/2+1)`单个项就需要用快速幂来做
如果k为偶数，即sum(k,p)有奇数项的时候
sum(k,p)=p*sum(k-1,p)+1;//秦九邵算法

参考视频: y总b站视频