包除原理とは数え上げ組合せ論における基本的な結果のひとつです。
2つの有限集合 A と B の和集合に属する元の数を計算するには、まずそれぞれに属する元の数 |A| と |B| を足しあわせた後、それらの共通部分に属する元の数 |A ∩ B| を引き去ればよいです。両者の合計から重複を取り除くという考え方です。
|A ∪ B| = |A|＋ |B| – |A ∩ B|
|A ∪ B ∪ C| = |A| + |B| + |C| – |A ∩ B| – |B ∩ C| – |C ∩ A| + |A ∩ B ∩ C|
1 から 100 までの自然数で 2 または 3 の倍数の個数を求めよ。
100 までならループを回して実際に割り切れる自然数の数を数える方法でも問題ないかもしれません。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
using System; public class Program { static void Main() { int ans = 0; for (int i = 1; i <= 100; i++) { if (i % 2 == 0 || i % 3 == 0) ans++; } Console.WriteLine(ans); } } |
では 100 までではなくもっと大きな数になったらどうでしょうか？
1 から 10^9 までの自然数で 2 または 3 の倍数の個数を求めよ。
これだと実際にループを回していては制限時間以内には終わりません。
2 の倍数の個数であれば 10^9 を 2 で割り端数を切り捨てれば求めることができます。3 の倍数の個数も同様に求めることができます。しかし単純に（2 の倍数の個数）+（3 の倍数の個数）が答えにはなりません。なかには 2 の倍数であり 3 の倍数でもある整数も存在し、単純にたすだけではこれらを2回カウントしてしまっています。（2 の倍数の個数）+（3 の倍数の個数）-（2 と 3 の公倍数の個数）が答えです。
|
1 2 |
int n = 100; int ans = n / 2 + n / 3 - n / 6; |
では 2 または 3 または 5 の倍数の個数であればどうなるでしょうか？
この場合は（2 の倍数の個数）+（3 の倍数の個数）+（5 の倍数の個数）から（2 と 3 の公倍数の個数）と（3 と 5 の公倍数の個数）と（2 と 5 の公倍数の個数）を引いてしまうと、今度は（2 と 3 と 5 の公倍数の個数）を多く引きすぎてしまうのでこれをたさなければなりません。
|
1 2 |
int n = 100; int ans = n / 2 + n / 3 + n / 5 - n / 6 - n / 15 - n / 10 + n / 30; |
もう少しこれを一般化して考えると（偶数個の自然数の公倍数の個数）を引き、（奇数個の自然数の公倍数の個数）を足せばよいということに気がつきます。
自然数 N と数列 A が入力される。
1 から N までの自然数で A_i で割り切れる数の個数を求めよ。
自然数 a と b の公倍数の個数であれば N を（a と b の最小公倍数）で割れば求めることができます。そこでまず最小公倍数を求める処理を定義します。最小公倍数は a と b の積を a と b の最大公倍数で割れば求めることができます。最大公約数は以下のようにユークリッドの互除法で求めることができます。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 |
using System; using System.Collections.Generic; public class Program { // 2つの自然数の最大公約数を求める（公倍数を求めるときに必要） static long GCD(long a, long b) { while (a > 0 && b > 0) { if (a < b) b = b % a; else a = a % b; } return Math.Max(a, b); } } |
複数の自然数の最小公倍数は2つの自然数の最小公倍数を求める処理を繰り返すことで求めることができます。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 |
public class Program { // 2つの数の最小公倍数を求める static long LCM(long a, long b) { return a / GCD(a, b) * b; } // 3つ以上の数の最小公倍数を求める static long LCM(List<long> values) { long ret = 1; foreach(long v in values) ret = LCM(ret, v); return ret; } } |
数列のなかから1個以上の要素を取り出す組み合わせを作り、そのときの要素数が偶数か奇数かで解を加算するか減算するかを決めます。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 |
public class Program { static void Main() { long N = long.Parse(Console.ReadLine()); long[] arr = Console.ReadLine().Split().Select(_ => long.Parse(_)).ToArray(); long ans = 0; for (int i = 1; i < 1 << arr.Length; i++) { int count = 0; // i を 2進法 に変換して 「1」の桁の個数を数える List<long> values = new List<long>(); for (int k = 0; k < arr.Length; k++) { if (((i >> k) & 1) == 1) { values.Add(arr[k]); // 何の最小公倍数を求めるか？ count++; } } long lcm = LCM(values); if (count % 2 == 1) ans += N / lcm; else ans -= N / lcm; } Console.WriteLine(ans); } } |
