等比数列求和推导及优化
等比数列求和公式： 推导： 所以 那么 则 如果q==1就特判输出q*n
但是这样有一个缺点就是如果答案要取模，时间复杂度就会难以估计，有时就会变得很大，导致超时。
代码实现时间复杂度：O(log(n+1))
核心代码(取模)如下：
ans=qsm_(n,m+1)-1;//调快速幂 while (ans%(n-1)) ans+=tt;//取模后ans可能不可以被n-1整除，所以不停修正ans直到ans可以被n-1整除。 ans=(ans/(n-1))%tt;
=============================================================================
等比数列求和分治思想： 利用分治思想可以将等比数列求和在时间复杂度上变得更加稳定(无论是否取模)，但是在不取模时，时间复杂度没有用公式快。 推导：设 则 分类讨论： n为奇数： n为偶数：
上述答案调递归即可 所以答案就是
代码实现时间复杂度：O(log(n)* log(n))
核心代码(取模)如下：
int dfs_(int x,int b)
{
if (b==0) return 0;//0特判
if (b==1) return x%tt;
int sum=dfs_(x,b/2),tot=0;
if (b&1) tot=qsm_(x,b);//奇偶性判断
return (sum*(1+qsm_(x,b/2))%tt+tot)%tt;
}
