等比数列求和的二分法

常见问题:给定整数M,等比数列$\{{a_n}\}$,求其前n项和对M的模

朴素的想法,我们可以用等比数列求和公式$S_n=\frac {a_1(1-q^n)}{1-q}$求得和再模除M,但是计算过程中取模导致分母下面的1-q不能直接除,要求1-q的乘法逆元;

这里介绍另一种思路,就是使用二分的思想,很像矩阵快速幂
首先,我们先讨论一个简单的问题:
求$a^1+a^2+a^3+a^4+a^5+a^6+a^7+a^8$的和
提取公因式,我们能把原式变为
$(a^1+a^2+a^3+a^4)(1+a^4)$
进一步变换为$(a^1+a^2)(1+a^2)(1+a^4)$
$=a(a+a^1)(1+a^2)(1+a^4)$
我们把这种等比数列前$2^k$项和记为$S(k)$有递推式$S(k)=S(k-1)(1+a^{2^{k-1}})$
这是二分法的关键,也就是说我们能在log(n)的时间内求出等比数列前$2^k$项的和

当我们要求的不是前2的整数次幂的时候,我们将n分解为2的整次幂的和:
比如求前等比数列11项的和,我们将11(二进制表示:1011)分解为1+2+8(二进制表示1+10+1000)
前11项的和可以表示为:
$(a^1)+(a^2+a^3)+(a^4+a^5+a^6+a^7+a^8+a^9+a^{10}+a^{11})$
可进一步表示为
$a^0(a^1)+a^1(a^1+a^2)+a^3(a^1+a^2+a^3+a^4+a^5+a^6+a^7+a^8)$
即:$a^0S(0)+a^1S(1)+a^3S(3)$
Well done!我们又把原式分解成了多个$a^xS(y)$的和

在这里可能可能会有一个小小的疑问,就是$a^xS(y)$中的x和y是怎么确定的,这里我是参考的矩阵快速幂的思想,x就是已经处理的指数的和,y根据当前处理的比特位置决定
一个快速幂大概这么写

注意,这里面的power一直充当$a^{2^k}$的角色,在等比数列求和中,他担任的功能还包括提供$S(k)=S(k-1)(1+a^{2^{k-1}})$中的$2^{k-1}$
下面是完整的样例程序: