病毒分裂（Dec. 1st, 2018）

数论

题目来源：当日考试T1
题意：求

$$(\sum_{i = 0}^{n - 2}k^i)\%p$$
思路：
1. 分治。
分离1。
以样例5 3 7为例：
$$\sum_{i=1}^{3-2=1}5^i+1=5+1=6$$
以样例2 8 23为例：
$$\sum_{i=1}^{8-2=6}2^i= \sum^{\lfloor\frac{6}{2}\rfloor}_{i=1}2^i+ \sum^{6}_{i=\lfloor\frac{6}{2}\rfloor+1}2^i= \sum^{3}_{i=1}2^i+\sum^{6}_{i=4}2^i= \sum^{3}_{i=1}2^i\times (2^{\lfloor\frac{6}{2}\rfloor}+1)= \sum^{3}_{i=1}2^i\times (2^3+1)$$
$$\sum_{i=1}^{3}2^i= \sum^{\lfloor\frac{3}{2}\rfloor}_{i=1}2^i+ \sum^{3}_{i=\lfloor\frac{3}{2}\rfloor+1}2^i= \sum^{1}_{i=1}2^i+\sum^{3}_{i=2}2^i= \sum^{1}_{i=1}2^i\times (2^{\lfloor\frac{3}{2}\rfloor}+1)+2^3= \sum^{1}_{i=1}2^i\times (2^{1}+1)+2^3$$
$$∵\sum^{1}_{i=1}2^i=2$$
$$∴\sum_{i=1}^{3}2^i=2\times 3+8=14$$
$$∴\sum_{i=1}^{6}2^i=14\times 9=126$$
$$∴\sum_{i=0}^{6}2^i=126+1=127$$