Kazun の競プロ記録

競技プログラミングに関する様々な話題を執筆します.

AtCoder Beginner Contest 284 D問題 Happy New Year 2023

AtCoder ABC284 ABC D問題 400 pts

問題

atcoder.jp

提出解答

atcoder.jp

問題の概要

与えられる正の整数 N はある異なる素数 p,q を用いて N=p^2 q と表せる.

p,q を求めよ.

T 個のマルチテストケース

制約

  • 1 \leq T \leq 10
  • 1 \leq N \leq 9 \times 10^{18}
  • N はある異なる整数 p,q を用いて N=p^2 q と表せる.

解法

ある異なる素数 p,q を用いて N=p^2 q と表せるとき, \min(p,q) \leq \sqrt[3]{N} である. 実際, \min(p,q) \lt \sqrt[3]{N} の場合,

N=p\^2 q \lt \sqrt[3]{N}^2 \cdot \sqrt[3]{N}=N

より, N \lt N となってしまうからである.

よって, p,q のうちの少なくとも一方は \sqrt[3]{N} 以下であるから, その \min(p,q) 及びそれが p,q のどちらかであるかを全探索すればよい.

  • r=2,3, \dots の順に以下を行う.
    • N が r の倍数ならば, \min(p,q)=r であるため, r=p か r=q かを確定させる.
      • N が r^2 の倍数ならば, p=r である. よって, q=\frac{N}{r^2} である.
      • N が r^2 の倍数でなければ, q=r である. よって, p=\sqrt{\frac{N}{r}} である.
      • どちらの場合にしてもこの時点で探索を終了し, (p,q) を出力する.

このアルゴリズムは上で求めた理論により, O(\sqrt[3]{N}) 時間で求める事ができる.

これを独立に T 個のテストケースについて求めれば良い.