快速等比数列求和
1.等比数列求和公式
- 要求给定的取余的数是质数，能求出逆元
2.递归分解
-
如果有偶数个，那么分解成两半，左边就为\(a_0+a_0q+a_0q^2...+a_0q^{n/2}\)，另一半为\(a_0q^{n/2+1}+a_0q^{n/2+2}+a_0q^{n/2+3}...+a_0q^{n}\)，令等比数列求和为一个函数\(f(n)\)，就有\(f(n)=f(n/2)*q^{n/2}\)
-
如果有奇数个，那么将其分解成\(f(n-1)*q+a_0\)
如果有偶数个，那么分解成两半，左边就为\(a_0+a_0q+a_0q^2...+a_0q^{n/2}\)，另一半为\(a_0q^{n/2+1}+a_0q^{n/2+2}+a_0q^{n/2+3}...+a_0q^{n}\)，令等比数列求和为一个函数\(f(n)\)，就有\(f(n)=f(n/2)*q^{n/2}\)
如果有奇数个，那么将其分解成\(f(n-1)*q+a_0\)