等比数列求和

写在前面, 这里的所有算法都是求从0次方开始求和的等比数列

如果要计算从1次方开始的等比数列之和sum - 1即可

递归分治算法 o(logk) k为最大幂指数

int qmi(int a, int k)
{
    int res = 1;
    while (k)
    {
        if (k & 1) res = res * a ;
        a = a * a;
        k >>= 1;
    }
    return res;
}

/*
递归算法求等比数列和 p为底数, k为最高次幂 - 1或者说项数

sample cin 2 3
sample cout 7
*/
int sum(int p, int k)
{
    if (k == 1) return 1;
    if (k % 2 == 0) return (1 + qmi(p, k / 2)) * sum(p, k / 2);
    return (sum(p, k - 1) + qmi(p, k - 1)) ;
}

循环算法 o(n)

/*
t 为最高指数或者说是项数
p 为底数

sample cin 2 3
sample cout 15
*/
ll sum (int p, int t)
{
    ll m = 1;
    while(t -- ) m = (m * p + 1);

    return m;
}

快速幂迭代算法 o(nlogn) n为项数