第2回は, 約数系包除を使うある問題について, 典型的な方法と, 包除原理を用いたもう1通りの解法を解説します. 次の問題を2通りで解いてみます. 例題2(想定Diff 1500) 自然数が与えられます. 集合の要素の数が以上である部分集合について, の最大公約数がであるものは何通りありますか?ただし, 答えは非常に大きくなる可能性があるのでで割った余りを求めてください. 時間制限:秒, メモリ制限:GB 制約: 入力:4 → 出力:10 の通りあります. まずは, DP(動的計画法)を使う方法を考えてみます. 典型テクニックとして, :の部分集合であって, 要素の数が以上で, そのすべての要…