結果

問題 No.2449 square_permutation
ユーザー Nikkuniku029
提出日時 2023-09-01 18:50:26
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 2,359 bytes
コンパイル時間 300 ms
コンパイル使用メモリ 82,244 KB
実行使用メモリ 100,784 KB
最終ジャッジ日時 2025-01-03 06:55:02
合計ジャッジ時間 7,171 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 1 WA * 20
権限があれば一括ダウンロードができます

ソースコード

diff # 

class eratosthenes:
    def __init__(self, N: int) -> None:
        '''
        Nまでの素数を列挙
        Parameters
        ----------
        N:int
        '''
        self.N = N
        self.isprime = [True]*(N+1)
        self.minfactor = [-1]*(N+1)
        self.isprime[1] = False
        self.minfactor[1] = 1
        self.mobius = [1]*(N+1)
        self.primecnt = 0
        # ふるう
        for p in range(2, self.N+1):
            if not self.isprime[p]:
                continue
            self.minfactor[p] = p
            self.mobius[p] = -1
            self.primecnt += 1
            for q in range(2*p, N+1, p):
                self.isprime[q] = False
                if self.minfactor[q] == -1:
                    self.minfactor[q] = p
                if (q//p) % p == 0:
                    self.mobius[q] = 0
                else:
                    self.mobius[q] = -self.mobius[q]

    def factorize(self, n: int) -> list:
        '''
        nの素因数分解
        O(logn)
        Parameters
        ----------
        n:int
        '''
        res = []
        while n > 1:
            p = self.minfactor[n]
            exp = 0
            while self.minfactor[n] == p:
                n //= p
                exp += 1
            res.append((p, exp))
        return res

    def divisors(self, n: int) -> list:
        '''
        nの約数列挙
        O(sigma(n))~O(n^(1/3))
        Parameters
        ----------
        n:int
        '''
        res = [1]
        factor = self.factorize(n)
        for p, e in factor:
            M = len(res)
            for i in range(M):
                v = 1
                for _ in range(e):
                    v *= p
                    res.append(res[i]*v)
        return res


N = int(input())
ER = eratosthenes(N+1)
ans = [i for i in range(N+1)]
changed = [False]*(N+1)
Squares = set()
for x in range(1, N+1):
    if pow(x, 2) > N:
        break
    Squares.add(pow(x, 2))

for i in range(N, 0, -1):
    factor = ER.factorize(i)
    j = 1
    for p, e in factor:
        if e % 2 == 0:
            continue
        j *= p
    if j == 1 and Squares:
        j = min(Squares)
        Squares.discard(j)
    if changed[j]:
        continue
    ans[j], ans[i] = i, j
    changed[j] = True
    changed[i] = True
    Squares.discard(i)
    Squares.discard(j)
print(*ans[1:])
0