ユニークビジョンプログラミングコンテスト2023 春 (AtCoder Beginner Contest 300) D - AABCC (400)
$ \sqrt{N}以下の素数を列挙する
それぞれの$ cについて以下を行う
$ c^2 \gt nなら終了
それぞれの$ aについて以下を行う
$ c^2a^2 \gt nなら終了
$ a^2bc^2 \le nになる$ bの個数を求める
二分探索で求まる
最初に列挙した素数の数を$ Pとすると$ \mathcal{O}(P \log P)となり、$ Pは最大78498個だが、実際には枝刈りなどでそこまで回らず間に合う
問題: https://atcoder.jp/contests/abc300/tasks/abc300_d
提出: https://atcoder.jp/contests/abc300/submissions/41035905
#ユニークビジョンプログラミングコンテスト2023春 #ユニークビジョンプログラミングコンテスト #ABC300 #400pt #D #ABC #AtCoder
#素数