betrue12 https://blog.hatena.ne.jp/betrue12/ ARMERIA https://betrue12.hateblo.jp/ AtCoder プログラミング 競技プログラミング お題箱より。 F - Coprime Present 解法 互いに素であるという条件を扱うときには、素因数だけに注目することで考慮すべき対象の個数を減らせる場合があります。2つの正整数が互いに素であることと共通の素因数を持たないことは同値です。 集合 とします。求めるべき答えは、 の部分集合のうち、どの相異なる2つの要素も共通の素因数を持たないものの個数です。そのため考えるべき素因数は、 の要素のうち2つ以上のものが持っている素因数だけで十分です。 の要素が連続する整数であり、その最大値と最小値の差が 以下と小さいことに注目します。 以上の素数 について、 に の倍数が2つ以上含まれることはあ… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Fbetrue12.hateblo.jp%2Fentry%2F2021%2F03%2F28%2F154410" title="AtCoder Beginner Contest 195 F - Coprime Present - ARMERIA" 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/106916089/1592411661884548 Hatena Blog https://hatena.blog 2021-03-28 15:44:10 rich https://betrue12.hateblo.jp/entry/2021/03/28/154410 1.0 100%