E - Sequence Sum ～数列のサイクル検出（位置と長さ）～

• Quiz
  • https://atcoder.jp/contests/abc179/tasks/abc179_e
• AC
  • https://atcoder.jp/contests/abc179/submissions/16895230
• 解説
  • Mが小さいので十分な長さの数列を作ればサイクルに入る
  • Nが大きいが、サイクル分はまとめて処理できるのでO(M)となる
  • ライブラリ化した
• 言葉
  • サイクルは「循環」、ループは「輪」なのでサイクルの方が適切っぽい
  • （ループに入る、とか言いやすいけれどね）

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;
}