semiexp https://blog.hatena.ne.jp/semiexp/ Algorithmer’s note https://semiexp.hatenadiary.org/ Algorithm TopCoder 問題 約数に1以外の平方数を含まないような数を「square-free number」と呼ぶ。各要素がsquare-free numberで、要素の積もsquare-free numberであるような整数の集合は、square-free setである。1〜K個の要素を含み、各要素が2〜Nの範囲にあるようなsquare-free setの数を求めよ。 解法 square-free setの要素の積を素因数分解してみると、同じ素数は高々1回しか現れない。これを利用して、「N以下の素数が並んでる中から適当に積がN以下になるように取るという操作をK回以下行う」場合の数を求めればいいことがわかる。 ここ… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Fsemiexp.hatenadiary.org%2Fentry%2F20110413%2F1302694543" title="TopCoder SRM440 Div1Hard - Algorithmer’s note" 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 2011-04-13 20:35:43 rich https://semiexp.hatenadiary.org/entry/20110413/1302694543 1.0 100%