等比数列求和

编程中计算等比数列求和一般不用数学上的公式

int gao(int r, int n) // r**0 + r**1 + ... + r**(n-1) = (r**n - 1) / (r - 1) 除法可能没有逆元
{
    if (n == 0)
    {
        return 0;
    }
    if (n % 2 == 0)
    {
        // r**0 + r**1 + r**2 + r**3 + r**4 + r**5
        // r**0 * (r + 1) + r**2 * (r + 1) + r**4 * (r + 1)
        // (r**0 + r**2 + r**4) * (r + 1)
        return gao(r * r % p, n / 2) * (r + 1) % p;
    }
    else
    {
        // r**0 + r**1 + r**2 + r**3 + r**4
        // (r**0 + r**1 + r**2 + r**3) * r + 1
        return (gao(r, n - 1) * r + 1) % p;
    }
}

这个等比数列求和方法，可以用于矩阵的等比数列求和