[ABC293E] Geometric Progression 题解

· · 题解

本题可以使用分治思想。

令 S_n 为 \sum\limits_{i=1}^n A^i，则我们可以分类讨论：

  1. 当 n 为偶数时，
\begin{aligned} S_n &=\sum_{i=1}^n A^i\\ &=\sum_{i=1}^{n/2} A^i+A^{n/2}\sum_{i=1}^{n/2} A^i\\ &=\left(\sum_{i=1}^{n/2}A^i\right)\left(A^{n/2}+1\right)\\ &=S_{n/2}\left(A^{n/2}+1\right) \end{aligned}
  1. 当 n 为奇数时，
\begin{aligned} S_n &=\sum_{i=1}^n A^i\\ &=\sum_{i=1}^{n-1} A^i+A^n\\ &=S_{(n-1)/2}\left(A^{(n-1)/2}+1\right)+A^n \end{aligned}

上述二式可以递归求解，答案最后加上 A^0=1 即可。

注意 x=1 和 m=1 的情况，需要特判。

放代码：

#include<bits/stdc++.h>
#define int long long
using namespace std;
int m;
int qpow(int a,int b){
  int r=1;
  while(b){
    if(b&1)r=r%m*a%m;
    a=a%m*a%m; b>>=1;
  }
  return r;
} // 快速幂
int f(int a,int x){
  if(!x)return 0; // x=1 时如果不加这行会 RE
  if(x==1)return a%m;
  if(x&1)return (f(a,x>>1)*(qpow(a,x>>1)+1)%m+qpow(a,x))%m;
  else return f(a,x>>1)*(qpow(a,x>>1)+1)%m;
  // 套公式
} // f(a,x) 表示解法描述中的 S[x]
main(){
  ios::sync_with_stdio(false);
  int a,x; cin>>a>>x>>m;
  cout<<(f(a,x-1)+1)%m<<endl;
  return 0;
}