🟫

ABC284-D: Happy New Year 2023 解説

2023/01/08に公開約600字

問題

T個のテストケースについて次の問題を解いてください
正整数Nが与えられます.
N = p^2q(p, qは相異なる素数)です.
pqを求めてください
https://atcoder.jp/contests/abc284/tasks/abc284_d

解説

  • (前提) 32bit整数(int)だと扱いきれないので,64bit整数(long long)を使う必要がある
  • Nの制約が1 \leq N \leq 9 \times 10^{18}なので工夫する必要がある
  • pqのうち,少なくとも片方が3 \times 10^6以下であることを使う
    • 両方が3 \times 10^6を超える場合,N(3 \times 10 ^ 6) ^ 3 = 27 \times 10^{18}を超えるため,制約違反となる
  • どちらか片方を決めるともう片方も決まるので,それを用いて判定する
    • 小さい方から順に判定するようにすると,そもそも素数か判定する必要がない(C++が高速だからかも?)
      • N = p^2qより,Nを割り切れる数はp, q, p^2, pq, p^2qしか存在しないため,小さい方から判定するとpqか小さい方が先に現れる

コード

https://atcoder.jp/contests/abc284/submissions/37864047

GitHubで編集を提案

Discussion

ログインするとコメントできます