ユニークビジョンプログラミングコンテスト2023 春 (AtCoder Beginner Contest 300) G - P-smooth number (600)
コンテスト中の考察
包除原理?
作れる素数の個数をDPしようにもそちらも指数オーダーになりそう
解説の解法
サンプル2が最悪ケース
これで間に合えば全てで間に合う
半分全列挙する
二つのグループを作り、各素数$ pについて要素数が少ない方に$ pを$ Nを越えない間追加する
最後に片方のグループの各要素について、もう片方の要素とかけて$ Nを超えない個数を二分探索で求める
問題: https://atcoder.jp/contests/abc300/tasks/abc300_g
提出: https://atcoder.jp/contests/abc300/submissions/41055286
#ユニークビジョンプログラミングコンテスト2023春 #ユニークビジョンプログラミングコンテスト #ABC300 #600pt #G #ABC #AtCoder
#半分全列挙