d_tutuz https://blog.hatena.ne.jp/d_tutuz/ 数学/競プロメモ https://tutuz.hateblo.jp/ 問題 https://beta.atcoder.jp/contests/colopl2018-qual/tasks/colopl2018_qual_c [a, b] の数から 0 個以上の要素を選んで集合 S とする。集合 S に含まれる要素はそれぞれ互いに素である。このような集合 S は何通りあるか？ 考え方 以下の 2 つ考えられる。 (i) [a, b] を全探索 最大 36 個の要素で全探索をすると 236 ≒ 7 * 1010 となる。ただし実は全探索する過程で、集合 S に含めることのできない要素については枝刈りされるので dfs で全探索することができる。 Submission … 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Ftutuz.hateblo.jp%2Fentry%2F2018%2F09%2F21%2F222736" title="COLOCON -Colopl programming contest 2018-：すぬけそだて――ごはん―― - 数学/競プロメモ" 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 2018-09-21 22:27:36 rich https://tutuz.hateblo.jp/entry/2018/09/21/222736 1.0 100%