結果

問題 No.3441 Sort Permutation 2
コンテスト
ユーザー 👑 potato167
提出日時 2026-01-04 13:37:36
言語 PyPy3
(7.3.17)
結果
AC  
実行時間 195 ms / 2,000 ms
コード長 1,065 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 244 ms
コンパイル使用メモリ 82,340 KB
実行使用メモリ 126,776 KB
最終ジャッジ日時 2026-02-06 20:51:35
合計ジャッジ時間 9,364 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 41
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

import sys
from math import gcd

def main():
    sys.setrecursionlimit(1_000_000)
    input = sys.stdin.readline

    N = int(input().strip())
    P = [0] + list(map(int, input().split()))

    visited = [False] * (N + 1)

    # F[g] = sum of (L-1) over cycles whose gcd-diff is g
    F = [0] * (N)  # indices 0..N-1 (g is in 1..N-1)

    for i in range(1, N + 1):
        if visited[i]:
            continue
        # traverse cycle of permutation i -> P[i]
        cur = i
        pos = []
        while not visited[cur]:
            visited[cur] = True
            pos.append(cur)
            cur = P[cur]

        L = len(pos)
        if L <= 1:
            continue

        base = pos[0]
        g = 0
        for x in pos[1:]:
            g = gcd(g, abs(x - base))
        # g is in 1..N-1
        F[g] += (L - 1)

    ans = [0] * (N)
    for k in range(1, N):
        s = 0
        for m in range(k, N, k):
            s += F[m]
        ans[k] = s

    out = "\n".join(str(ans[k]) for k in range(1, N))
    print(out)

if __name__ == "__main__":
    main()
0