题目大意给定整数\(A,X,M\)，求\(\sum\limits^{X-1}_{i=0}A^i\)对\(M\)取模的值。数据范围：\(1\leA,M\le10^9\)，\(1\leX\le10^{12}\)。题目分析直接算显然

由于模数不一定是大质数，我们不能直接套等比数列求和公式。换一种思路，数列\(\langle1,A,A^2,\cdots,A^{X-1}\rangle\)可以看做线性递推，因此设计矩阵：\[\boldsymbolT=\b

[ABC293E]GeometricProgression题解神中神数论题目描述给定整数\(A,X,M\)，求\[\sum_{i=0}^{X-1}A^i\bmodM\]\(1\leA,M\le10^9\)\(1\leX\le10^