等比数列求和推导及优化

3/8/2017来源:ASP.NET技巧人气:949

等比数列求和公式:这里写图片描述 推导:这里写图片描述 所以这里写图片描述 那么这里写图片描述这里写图片描述 如果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; }