E - Sequence Sum ~サイクル検出(位置と長さ)~

f:id:peroon:20200920004710p:plain

code

// ※サイクル!=ループ

// サイクルを見つけてあげましょう
// 入力:サイクルが存在するであろう数列
// 出力:サイクルの開始index, サイクルの長さ
PII find_cycle(VI& A){
  ll N = SZ(A);
  map<ll,VI> mp;
  rep(i,N){
    ll a = A[i];
    mp[a].push_back(i);
    if(mp[a].size()>1){
      // found cycle
      ll len = mp[a][1] - mp[a][0];
      ll cycle_start_index = mp[a][0];
      return {cycle_start_index, len};
    }
  }
  return {-1,-1};
}

int main(){
  cin.tie(0);
  ios::sync_with_stdio(false);

  // input
  ll N,X,M;
  cin>>N>>X>>M;

  ll a = X;
  VI A;
  rep(i,200200){
    A.push_back(a);
    a = (a*a)%M;
  }
  auto pa = find_cycle(A);
  ll cycle_start_index = pa.first;
  ll cycle_len = pa.second;
  ll cycle_sum = 0;
  FOR(i,cycle_start_index, cycle_start_index+cycle_len){
    cycle_sum += A[i];
  }
  
  ll sum=0;
  // サイクルに入る前
  rep(i,cycle_start_index){
    sum += A[i];
  }

  ll rest = N-cycle_start_index;
  ll num = rest / cycle_len; // サイクル数
  sum += num * cycle_sum;

  // サイクルのあまり
  ll r = rest%cycle_len;
  FOR(i,cycle_start_index, cycle_start_index+r){
    sum += A[i];
  }
  p(sum);
  return 0;
}