結果

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

ソースコード

diff #
raw source code 

import sys
input = sys.stdin.readline

from math import gcd

# 線形篩。エラトステネスの篩を線形にできる。
MAX=3*10**5+10 # 使いたい最大値を指定
Sieve=[-1]*MAX
Primes=[]

for i in range(2,MAX):
    if Sieve[i]==-1:
        Primes.append(i)
        Sieve[i]=i

    for p in Primes:
        if p*i>=MAX or p>Sieve[i]:
            break
        else:
            Sieve[p*i]=p


# 素因数分解
def fact(x):
    D=dict()
    while x!=1:
        k=Sieve[x]
        if k in D:
            D[k]+=1
        else:
            D[k]=1
        x//=k
    return D

# 約数列挙
def faclist(x):
    LIST=[1]
    while x!=1:
        k=Sieve[x]
        count=0
        while x%k==0:
            count+=1
            x//=k

        LIST2=[]
        for l in LIST:
            for i in range(1,count+1):
                LIST2.append(l*k**i)
        LIST+=LIST2

    return LIST


N=int(input())
P=list(map(int,input().split()))
for i in range(N):
    P[i]-=1

USE=[0]*N

LIST=[]
for i in range(N):
    if USE[i]==1:
        continue

    Q=[i]

    while True:
        Q.append(P[Q[-1]])
        USE[Q[-1]]=1

        if Q[0]==Q[-1]:
            break

    LIST.append(Q)

#print(LIST)

ANS=[0]*N
for X in LIST:
    GCD=0
    for i in range(1,len(X)):
        k=X[i]-X[i-1]
        GCD=gcd(GCD,k)

    if GCD==0:
        continue

    for x in faclist(GCD):
        ANS[x]+=len(X)-2

print("\n".join(map(str,ANS[1:])))
0