結果

問題 No.3441 Sort Permutation 2
コンテスト
ユーザー npnp
提出日時 2026-02-06 22:36:50
言語 C++23
(gcc 15.2.0 + boost 1.89.0)
結果
WA  
実行時間 -
コード長 6,860 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 6,422 ms
コンパイル使用メモリ 387,268 KB
実行使用メモリ 18,132 KB
最終ジャッジ日時 2026-02-06 22:37:23
合計ジャッジ時間 29,212 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 14 WA * 27
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

//Compile Options
# pragma GCC target("avx2")
# pragma GCC optimize("O3")
# pragma GCC optimize("unroll-loops")

//libraries
#include <bits/stdc++.h>

//templates

// ---------- 基本 ----------
#define ll long long
#define ull unsigned long long
#define ld long double

#define pii pair<int,int>
#define pll pair<ll,ll>

// ---------- for 系 ----------
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define rep1(i,n) for(int i=1;i<=(int)(n);i++)
#define rrep(i,n) for(int i=(int)(n)-1;i>=0;i--)
#define repi(i,a,b) for(int i=(int)(a);i<(int)(b);i++)

// ---------- コンテナ操作 ----------
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()

// ---------- sort ----------
#define srt(x) sort(all(x))
#define rsrt(x) sort(rall(x))

// ---------- sum ----------
#define sum(x) std::reduce(all(x))

// ---------- 出力補助 ----------
#define yes cout << "Yes\n"
#define no cout << "No\n"
#define YES cout << "YES\n"
#define NO cout << "NO\n"
#define print(a) cout << (a) << endl

// その他
#define append push_back


using namespace std;

template <class T>
void println_decimal(T value, int digits) {
    std::cout << std::fixed << std::setprecision(digits) << value << '\n';
}


//累積和
template <class T = long long>
struct CumulativeSum {
private:
    // pref[i] = 先頭から i 個分の和
    std::vector<T> pref;

public:
    CumulativeSum() {
        pref.push_back(T(0)); // pref[0] = 0
    }

    // 要素を末尾に追加
    void push_back(T x) {
        pref.push_back(pref.back() + x);
    }

    // 区間 [l, r] の和を返す
    T range_sum(int l, int r) const {
        //assert(0 <= l && l <= r && r < (int)pref.size());
        if (l<0 && r<0) return 0;
        if (l>=(int)pref.size()-1) return 0;
        if (l<0) l=0;
        if (r>=(int)pref.size()-1) r=(int)pref.size()-2;
        return pref[r+1] - pref[l];
    }

    // 現在の要素数
    int size() const {
        return (int)pref.size() - 1;
    }
};

//使い方
// CumulativeSum<long long> cs;
// cs.push_back(3);
// cs.push_back(5);
// cs.push_back(2);

// // [0,2] = 3+5+2
// cs.range_sum(0, 2);   // 10

// // [-5,1] → [0,1]
// cs.range_sum(-5, 1);  // 8

// // [2,10] → [2,2]
// cs.range_sum(2, 10);  // 2

// // 完全に外
// cs.range_sum(5, 7);   // 0




// const int N = 2*pow(10,4);

// vector<bool> isp(N+1, true);

// void sieve() {
//   isp[0] = false;
//   isp[1] = false;
//   for (int i=2; pow(i,2)<=N; i++) {
//     if (isp[i]) for(int j=2; i*j<=N; j++) isp[i*j] = false;
//   }
// }


//素因数分解
// const int N = 200000; // 必要に応じて変更
// vector<int> minp(N + 1);

// 最小素因数の前計算
// void sieve_minp() {
//     for (int i = 0; i <= N; i++) minp[i] = i;
//     minp[0] = 0;
//     minp[1] = 1;

//     for (int i = 2; i * i <= N; i++) {
//         if (minp[i] == i) { // i が素数
//             for (int j = i * i; j <= N; j += i) {
//                 if (minp[j] == j) minp[j] = i;
//             }
//         }
//     }
// }

// // x の素因数分解を返す
// // 戻り値: {素因数, 指数} の vector
// vector<pair<ll, ll>> pfWithMinp(ll x) {
//     vector<pair<ll, ll>> res;
//     while (x > 1) {
//         ll p = minp[x];
//         ll cnt = 0;
//         while (x % p == 0) {
//             x /= p;
//             cnt++;
//         }
//         res.push_back({p, cnt});
//     }
//     return res;
// }



ll exp10(int n){
    ll ans= 1;
    rep(i,n){
        ans*=10;
    }
    return ans;
}
unsigned GetDigit(unsigned num){
	unsigned digit = 0;
	while(num != 0){
		num /= 10;
		digit++;
	}
	return digit;
}



struct triplet
{
    /* data */
    ll first;
    ll second;
    ll third;
};

struct Eratosthenes {
    // テーブル
    vector<bool> isprime;
    
    // 整数 i を割り切る最小の素数
    vector<int> minfactor;

    // コンストラクタで篩を回す
    Eratosthenes(int N) : isprime(N+1, true),
                          minfactor(N+1, -1) {
        // 1 は予めふるい落としておく
        isprime[1] = false;
        minfactor[1] = 1;

        // 篩
        for (int p = 2; p <= N; ++p) {
            // すでに合成数であるものはスキップする
            if (!isprime[p]) continue;

            // p についての情報更新
            minfactor[p] = p;
            
            // p 以外の p の倍数から素数ラベルを剥奪
            for (int q = p * 2; q <= N; q += p) {
                // q は合成数なのでふるい落とす
                isprime[q] = false;
                
                // q は p で割り切れる旨を更新
                if (minfactor[q] == -1) minfactor[q] = p;
            }
        }
    }

    // pair (素因子, 指数) の vector を返す
    vector<pair<int,int>> factorize(int n) {
        vector<pair<int,int>> res;
        while (n > 1) {
            int p = minfactor[n];
            int exp = 0;

            // n で割り切れる限り割る
            while (minfactor[n] == p) {
                n /= p;
                ++exp;
            }
            res.emplace_back(p, exp);
        }
        return res;
    } 



    // 高速約数列挙
    vector<int> divisors(int n) {
        vector<int> res({1});

        // n を素因数分解 (メンバ関数使用)
        auto pf = factorize(n);

        // 約数列挙
        for (auto p : pf) {
            int s = (int)res.size();
            for (int i = 0; i < s; ++i) {
                int v = 1;
                for (int j = 0; j < p.second; ++j) {
                    v *= p.first;
                    res.push_back(res[i] * v);
                }
            }
        }
        return res;
    }
};



int main() {    
    ll N;
    cin >> N;

    Eratosthenes er(200001);

    vector<ll> A(N);

    rep(i,N){
        cin >> A[i];
        A[i]--;
    }

    //添字・中身でループ検出
    vector<bool> visited(N,false);
    vector<vector<ll>> loops;
    ll ans = 0;
    rep(i,N){
        if(visited[i]) continue;

        vector<ll> loop;
        ll cnt = 0;
        ll cur = i;
        while(!visited[cur]){
            visited[cur] = true;
            loop.push_back(cur);
            cur = A[cur];
            cnt++;
        }
        loops.push_back(loop);
        ans += cnt -1;
    }

    vector<int> res(N,0);
    vector<int> dv;
    
    
    rep(i,loops.size()){
        set<int> unique_divisors;
        rep(j,loops[i].size()){
            // cout << loops[i][j] << " ";
            dv = er.divisors(abs(loops[i][j]-loops[i][(j+1)%loops[i].size()]));

            rep(k,dv.size()){
                res[dv[k]]++;
                unique_divisors.insert(dv[k]);
            }
        }
        for(int d : unique_divisors){
            res[d]--;
        }
    }



    rep1(i,res.size()-1){
        print(res[i]);
    }




    

}
0