問題

ABC284 D - Happy New Year 2023

お気持ち

• $N = p^2q$と、$1 \leq N \leq 9 \times 10^{18}$の制約をしっかり変換していく

• 素数$\times$素数$\times$素数が$10^{18}$以下になる

  • 1つの素数は$10^{6}$以下？

    • 罠その1。この罠を設置した作問者は本当に性格が悪い…！！！やってくれますねぇ…！！！（褒め言葉）
      • $3\times10^7$くらいの素数$\times10^7$くらいの素数 $=10^{18}$以下
      • $3\times 3 \times 10^{15}$くらいの素数 $=10^{18}$以下
        • どこまで素数列挙すればええねーん！
          • 無事死亡(5ペナ=25分)

  • 素数のうちどちらか1つは$10^{6}$以下？

    • 正解ルート
      • じゃあとりあえず$10^6$以下の素数を用意して…
        • 罠その2。馬鹿め！！！かかりおったわ！！！
        • テストケースは高々10個しか無いんだから、全部10^6まで計算しても余裕っぽい感じ。
        • 制約ちゃんと読もうね！！！黒ココアさん制約ちゃんと読んでね！！！！！

• 自信を持って「$N = p^2q$の制約から、$\sqrt[3]{N}$まで見れば解決する！！！」って言い切って、そこに全体重を掛ける事ができるかの度胸試しみたいな問題だと感じました…

  • 素数リスト作ってごちゃごちゃしてペナ稼ぐくらいならえいやっと乗ってみたら上手く行ったのかもしれない…？
  • 考察は大事。思い切りも大事。（戒め）

ソースコード

T = int(input())

for i in range(T):
    N = int(input())
    limit_num = int(N ** (1 / 3) + 1)
    for num in range(2, limit_num):
        if N % num == 0:
            break
    if N % (num * num) == 0:
        p = num
        q = N // (num * num)
    else:
        p = int((N // num) ** (1 / 2))
        q = num
    print(p, q)