今回はABC206の「E – Divide Both」の解法を理解するために記事を書いています。
この問題の公式解説ではABC162のE問題が参照されており、こちらの有志解説記事では約数系包除が前提知識となっていました。
約数系包除は包除原理の派生らしいですがどちらも初見のため、まずは包除原理について理解していきます。
本記事では有志解説記事で紹介されていた包除原理についての偉大なスライドを参考にします。
包除原理は和集合の要素数を、積集合の要素数から求められるようになる等式です。
この等式では全ての奇数個の積集合の要素数を足し、全ての偶数個の積集合の要素数を引くと、和集合全体の要素数になると言っています。
等式を試すため、30以下の自然数の中で2か3か5の倍数である数の個数を考えます。
該当しない数は{1,7,11,13,17,19,23,29}の8個のため、該当する数は22個です。
Aを30以下の2の倍数の集合、Bを30以下の3の倍数の集合、Cを30以下の5の倍数の集合とすると、
となり、要素数が包除原理の右辺の結果と等しくなります。
包除原理の証明方法はいくつか有り、高校数学の美しい物語 – 包除原理の２通りの証明では二項定理による証明と数学的帰納法による証明が紹介されています。
二項定理による証明の方が好みだったため、個人ブログにて二項定理による証明を紹介しています。
【競プロ】包除原理-1
入会申込
ログイン
