drken1215 https://blog.hatena.ne.jp/drken1215/ けんちょんの競プロ精進記録 https://drken1215.hatenablog.com/ AOJ AOJ-ICPC350点 素数 素因数分解 エラトステネスの篩 エラトステネスの区間篩 数学(整数問題) 入力が定数個 数え上げ問題 制約:数値が10^6以下 エラトステネスの篩を用いた素因数分解の列挙 JAG AtCoder AOJ-ICPC JAG模擬地区 NoviSteps1D 貴重な区間篩の問題 問題へのリンク editorial 問題概要 2 つの正の整数 が与えられる。以下の条件を満たす整数 の個数を求めよ。 の相異なる素因数の個数が素数個 制約 考えたこと が小さいので、それを活かした解法が考えられそう。具体的には区間篩が使える。 に対して、 が素数ならば 以上 以下の整数 についてのみ prime_factors[ ].push_back() と更新していく というふうにする。それを元にして、各整数 を高速素因数分解していけば OK。計算量は エラトステネスの区間篩： 各整数の素因数分解： コード #include <bits/stdc++.h> using… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Fdrken1215.hatenablog.com%2Fentry%2F2020%2F11%2F02%2F152200" title="AOJ 2858 Prime-Factor Prime (JAG 模擬地区 2017 C) (1D, 350 点) - けんちょんの競プロ精進記録" class="embed-card embed-blogcard" scrolling="no" frameborder="0" style="display: block; width: 100%; height: 190px; max-width: 500px; margin: 10px 0px;"></iframe> https://cdn.user.blog.st-hatena.com/default_entry_og_image/80936665/1516148889515660 Hatena Blog https://hatena.blog 2020-11-02 15:22:00 rich https://drken1215.hatenablog.com/entry/2020/11/02/152200 1.0 100%