等比数列求和-分治法
题目
\((1 + p + p^2 + ...+ p^c) mod B\)
因为等比数列直接用求和公式会出现分数形式，不能对分子和分母进行mod运算，再做除法
mod只对加、减、乘具有分配律
若 c为奇数
\[1 + p + p^2 + ...+ p^c
\]
\[=（1 + p + p^2 + ..+p^{\frac{c-1}{2}）+ (p^{\frac{c+1}{2}} + p^{\frac{c+3}{2}} + ...+p^c})
\]
\[= (1 + p + p^2 + ..+p^{\frac{c-1}{2}}）+ p^{\frac{c+1}{2}} * (1 + p + p^2 + ..+p^{\frac{c-1}{2}})
\]
\[= (1 + p^{\frac{c+1}{2}}) * (1 + p + p^2 + ..+p^{\frac{c-1}{2}})
\]
\[= (1 + p^{\frac{c+1}{2}}) * sum(p, \frac{c-1}{2})
\]
若 c为偶数
\[1 + p + p^2 + ...+ p^c
\]
\[=（1 + p + p^2 + ..+p^{\frac{c}{2}-1）+ (p^{\frac{c}{2}} + p^{\frac{c}{2}+1} + ...+p^c})
\]
\[= (1 + p + p^2 + ..+p^{\frac{c}{2}-1}）+ p^{\frac{c}{2}} * (1 + p + p^2 + ..+p^{\frac{c-1}{2}}) + p ^ c
\]
\[= (1 + p^{\frac{c}{2}}) * (1 + p + p^2 + ..+p^{\frac{c-1}{2}}) + p ^ c
\]
\[= (1 + p^{\frac{c}{2}}) * sum(p, \frac{c-1}{2}) + p ^ c
\]
代码
ll ksm(ll a, ll b) {
ll ans = 1;
while(b) {
if(b & 1) {
ans *= a;
}
a *= a;
b >>= 1;
}
return ans;
}
ll sum(ll a, ll b) {
if(b == 0) return 1;
if(b == 1) return a;
if(b & 1) {
return ((1 + ksm(a, (b + 1) / 2)) * sum(a, (b - 1) / 2));
} else {
return ((1 + ksm(a, b / 2) * sum(a, (b - 1) / 2)) + ksm(a, b));
}
}