結果

問題 No.3441 Sort Permutation 2
コンテスト
ユーザー detteiuu
提出日時 2026-02-06 21:31:25
言語 PyPy3
(7.3.17)
結果
AC  
実行時間 385 ms / 2,000 ms
コード長 1,919 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 478 ms
コンパイル使用メモリ 82,564 KB
実行使用メモリ 124,360 KB
最終ジャッジ日時 2026-02-06 21:31:41
合計ジャッジ時間 13,846 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 41
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

from math import gcd

class UnionFind:
    def __init__(self,n):
        self.n = n
        self.parent_size = [-1]*n
 
    def leader(self,a):
        if self.parent_size[a] < 0:
            return a
        self.parent_size[a] = self.leader(self.parent_size[a])
        return self.parent_size[a]
 
    def merge(self,a,b):
        x, y = self.leader(a), self.leader(b)
        if x == y:
            return 
        if abs(self.parent_size[x]) < abs(self.parent_size[y]):
            x, y = y, x
        self.parent_size[x] += self.parent_size[y]
        self.parent_size[y] = x
        return 
 
    def same(self,a,b):
        return self.leader(a) == self.leader(b)
 
    def size(self,a):
        return abs(self.parent_size[self.leader(a)])
 
    def groups(self):
        result = [[] for _ in range(self.n)]
        for i in range(self.n):
            result[self.leader(i)].append(i)
        return [r for r in result if r != []]

def Eratosthenes(n):
    isPrime = [True]*(n+1)
    isPrime[0], isPrime[1] = False, False
    for i in range(2, n+1):
        if isPrime[i]:
            for j in range(i*i, n+1, i):
                isPrime[j] = False
    return isPrime

def fast_zeta(F):
    isPrime = Eratosthenes(len(F))
    for i in range(2, len(F)):
        if isPrime[i]:
            for j in range((len(F)-1)//i, 0, -1):
                F[j] += F[j*i]

def fast_mobius(F):
    isPrime = Eratosthenes(len(F))
    for i in range(2, len(F)):
        if isPrime[i]:
            for j in range(1, (len(F)-1)//i+1):
                F[j] -= F[j*i]

N = int(input())
P = list(map(int, input().split()))

UF = UnionFind(N)
for i, p in enumerate(P):
    p -= 1
    UF.merge(i, p)

G = UF.groups()
ans = [0]*N
for g in G:
    if len(g) == 1:
        continue
    GCD = g[1]-g[0]
    for i in range(1, len(g)-1):
        GCD = gcd(GCD, g[i+1]-g[i])
    ans[GCD] += len(g)-1

fast_zeta(ans)

print(*ans[1:], sep="\n")
0