kanpurin https://blog.hatena.ne.jp/kanpurin/ かんプリンの学習記録 https://kanpurin.hatenablog.com/ ABC 解説 競技プログラミング 数え上げ 典型 Python 数論 問題はこちら 問題概要 解説1 解説2 提出プログラム 感想 問題概要長さの正整数列が与えられる．以下の条件を満たすをすべて求めよ． すべてのを満たす整数について，である． 解説1となるのは，がの任意の素因数を持たないことと同じです．のすべての素因数を求めて，その素因数を持たない以上以下の整数を求められれば良いです． エラトステネスの篩を用いて，以上以下の素数であって，を素因数に持つようなが存在するようなものをで求めます．この素数に対して，以上以下であっての倍数であるような数を，同じくエラトステネスの篩の要領で消していけば残った数が答えとなります．全体の計算量はとなります．kanpurin.h… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Fkanpurin.hatenablog.com%2Fentry%2F2021%2F08%2F21%2F232035" title="ABC215 D - Coprime 2 - かんプリンの学習記録" class="embed-card embed-blogcard" scrolling="no" frameborder="0" style="display: block; width: 100%; height: 190px; max-width: 500px; margin: 10px 0px;"></iframe> Hatena Blog https://hatena.blog 2021-08-21 23:20:35 rich https://kanpurin.hatenablog.com/entry/2021/08/21/232035 1.0 100%