結果

問題 No.2449 square_permutation
ユーザー lam6er
提出日時 2025-03-20 20:20:36
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 739 ms / 2,000 ms
コード長 1,437 bytes
コンパイル時間 319 ms
コンパイル使用メモリ 82,608 KB
実行使用メモリ 263,628 KB
最終ジャッジ日時 2025-03-20 20:21:44
合計ジャッジ時間 13,629 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 21
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
from collections import defaultdict, deque

def main():
    N = int(sys.stdin.readline())
    if N == 0:
        print()
        return
    
    # Sieve of smallest prime factors
    max_n = N
    min_prime_factor = [0] * (max_n + 1)
    for i in range(2, max_n + 1):
        if min_prime_factor[i] == 0:
            min_prime_factor[i] = i
            for j in range(i*i, max_n +1, i):
                if min_prime_factor[j] == 0:
                    min_prime_factor[j] = i
    
    # Function to compute square-free part
    def compute_square_free(n):
        if n == 1:
            return 1
        res = 1
        while n > 1:
            p = min_prime_factor[n]
            count = 0
            while n % p == 0:
                count += 1
                n = n // p
            if count % 2 == 1:
                res *= p
        return res
    
    # Group numbers by their square-free part
    groups = defaultdict(list)
    for i in range(1, N+1):
        s = compute_square_free(i)
        groups[s].append(i)
    
    # Sort each group in descending order and convert to deque
    for s in groups:
        lst = sorted(groups[s], reverse=True)
        groups[s] = deque(lst)
    
    # Generate the permutation
    P = []
    for i in range(1, N+1):
        s = compute_square_free(i)
        val = groups[s].popleft()
        P.append(str(val))
    
    print(' '.join(P))

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