【AtCoder】反復処理の周期を求める方法

例題：典型90問058 - Original Calculator（★4）

• タイムスタンプ用の配列を用意する

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i, n) for (int i = 0; i < (n); ++i)

int digit_sum(int x) {
  int res = 0;
  while (x != 0) { res += x % 10; x /= 10; }
  return res;
}

int main() {
  int N; ll K;
  cin >> N >> K;
  
  const int mod = 100000;
  vector<int> nxt(mod), time_stamp(mod, -1);
  rep(i, mod) nxt[i] = (i + digit_sum(i)) % mod;
  int pos = N, cnt = 0;
  while (time_stamp[pos] == -1) {
    time_stamp[pos] = cnt;
    pos = nxt[pos]; cnt++;
  }
  
  if (time_stamp[pos] <= K) {
    int cycle = cnt - time_stamp[pos];
    K = (((K - time_stamp[pos] + 1) % cycle  + cycle - 1) % cycle) + time_stamp[pos];
  }
  
  rep(i, mod) if (time_stamp[i] == K) {
    cout << i << endl;
    return 0;
  }
}