結果

問題 No.3441 Sort Permutation 2
コンテスト
ユーザー V_Melville
提出日時 2026-02-06 21:58:58
言語 C++23
(gcc 15.2.0 + boost 1.89.0)
結果
AC  
実行時間 89 ms / 2,000 ms
コード長 861 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 3,392 ms
コンパイル使用メモリ 340,520 KB
実行使用メモリ 7,972 KB
最終ジャッジ日時 2026-02-06 21:59:15
合計ジャッジ時間 8,990 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 41
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <bits/stdc++.h>
#define rep(i, n) for (int i = 1; i <= (n); ++i)

using namespace std;
using ll = long long;

int main() {
    int n;
    cin >> n;
    
    vector<int> p(n+1);
    rep(i, n) cin >> p[i];
    
    vector<bool> used(n+1);
    vector<ll> cnt(n+1);
    
    rep(i, n) {
        if (used[i]) continue;
        int v = i;
        vector<int> vs;
        while (!used[v]) {
            used[v] = true;
            vs.push_back(v);
            v = p[v];
        }
        int l = vs.size();
        if (l <= 1) continue;
        int g = 0;
        int base = vs[0];
        for (int j = 0; j < l; ++j) {
            g = gcd(g, abs(vs[j]-base));
        }
        if (g) cnt[g] += l-1;
    }
    
    rep(k, n-1) {
        ll ans = 0;
        for (int i = k; i < n; i += k) ans += cnt[i];
        cout << ans << '\n';
    }
    
    return 0;
}
0