C - ℕ Coloring ～mex解法～

• Quiz
  • https://atcoder.jp/contests/arc115/tasks/arc115_c
• AC
  • https://atcoder.jp/contests/arc115/submissions/22316432
• 解説
  • editorialと違う別解でACしたので書いておく
  • 答えを左から（添字１から）埋めていく
  • 添字 i を素因数分解して約数一覧を得る（これは計算量 log(i) または sqrt(i) で済ませたい。どちらでも通る）
    • log(i) : 100ms
    • sqrt(i) : 256ms
  • その約数の箇所と同じ値を使ってはいけないのだから、それらの値のmexを割り当てればよい

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

    // 素因数分解の準備
    prepare_factorize();

    // input
    ll N;cin>>N;
    
    VI Ans = {0};
    FOR(i,2,N+1){
      // 約数一覧
      VI D = calc_devisors(i);
      set<ll> se;
      for(ll d : D){
        if(d==i)continue;
        se.insert(Ans[d-1]);
      }
      ll m = mex(se);
      Ans.push_back(m);
    }
    print_vector(Ans,+1);
    
    return 0;
}