[ABC293E] Geometric Progression 题解
神中神数论
题目描述
给定整数 \(A, X, M\)，求
\[\sum_{i= 0} ^ {X - 1}A^i\bmod M \]-
\(1 \le A, M \le 10^9\)
-
\(1\le X\le 10^{12}\)
Solution1
最酷炫的一个，分治。
可以发现
\[\sum_{i= 0} ^ {X - 1}A^i=\begin{cases} \sum_{i= 0} ^ {X - 2}A^i + A^{X-1} & ,X-1\bmod 2 \equiv 1 \\ \sum_{i = 0} ^ {\frac{X-1}2 }\times(A^{\frac{X-1}2} + 1) & ,X-1\bmod 2 \equiv 0 \end{cases} \]显然时间复杂度为 \(O(\log X)\)
int solve(int a, int k)
{
if(k == 1) return 1;
if(k % 2) return (solve(a, k - 1) + qmi(a, k - 1)) % mod;
return (solve(a, k / 2) * (qmi(a, k / 2) + 1)) % mod;
}
来自Jasper08大佬
Solution2
最好理解的方法，矩阵乘法。
若令 \(f_i = \sum\limits_{i=0}^{X-1}A^i\)，则有 \(f_i = Af_{i - 1} + 1\)。
显然可以用矩阵加速这个递推过程：
\[\begin{bmatrix} A & 1\\ 0 & 1 \end{bmatrix} \times \begin{bmatrix} f_{i-1}\\ 1 \end{bmatrix} = \begin{bmatrix} f_i\\ 1 \end{bmatrix} \]所以初始状态 \(f_1 = 1\)。
则有
\[\begin{bmatrix} A & 1\\ 0 & 1 \end{bmatrix}^{X-1} \times \begin{bmatrix} f_{1}\\ 1 \end{bmatrix} = \begin{bmatrix} f_X\\ 1 \end{bmatrix} \]时间复杂度：\(O(\log X)\)。
Solution3
最快的方法 / 最神仙的方法，同余方程。
若令 \(S = \sum_{i=0}^{X-1}A^i\)，则有 \(AS = \sum_{i=1}^XA_i\)
因此错位相减得到，\((A-1)S \equiv A^X-1\pmod {M(A-1)}\)，把 \(A-1\) 移过去求逆元不可行，因为 \(A-1\) 与 \(M\) 不一定互质，不一定存在逆元。
可以证明 \((A-1)|(A^X-1\bmod M(A-1))\)。
时间复杂度：\(O(\log M)\)
signed main()
{
if(A == 1)
{
write(X % mod);
return 0;
}
mod = mod * (A - 1);
int a = A, b = qmi(A, X);
b = (b + mod) % mod;
if(A - 1 == 0)
{
cout << 0 << endl;
return 0;
}
write(b / (A - 1));
return 0;
}
标签：begin,end,int,题解,sum,bmatrix,ABC293E,Geometric,mod From： https://www.cnblogs.com/MoyouSayuki/p/17207283.html来自 CTR_WU 大佬