包除原理とは数え上げ組合せ論における基本的な結果のひとつです。
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 までならループを回して実際に割り切れる自然数の数を数える方法でも問題ないかもしれません。
|
|
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 の公倍数の個数）が答えです。
|
|
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 の公倍数の個数）を多く引きすぎてしまうのでこれをたさなければなりません。
|
|
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); } } |
鳩でも分かるC#管理人からのお願い
できる仕事であれば請け負います。鳩でもわかるC#管理人はクラウドワークスに在宅ワーカーとして登録しています。お仕事の依頼もお待ちしております。
⇒ 仕事を依頼する
コメントについて
コメントで英語などの外国語でコメントをされる方がいますが、管理人は日本語以外はわからないので基本的に内容が理解できず、承認することもありません。それからへんな薬を売っているサイトやリンク先のサイトが存在しないというスパムコメントも多々あります。
Some people make comments in foreign languages such as English, but since the manager does not understand anything other than Japanese, he basically cannot understand the content and does not approve it. Please use Japanese when making comments.
そんななか日本語のコメントもいただけるようになりました。「○○という変数はどこで宣言されているのか？」「××というメソッドはどこにあるのか」「例外が発生する」「いっそのことソース丸ごとくれ」という質問ですが、管理人としては嬉しく思います。「自分が書いた記事は読まれているんだな」と。疑問点には可能な限り答えます。記事に問題があれば修正いたします。
そのうえでお願いがあります。「匿名」という味も素っ気もない名前ではなく、捨てハンでいいのでなにかハンドルネームをつくってほしいと思います。
管理人のモチベーションアップのために
よろしければご支援お願いします。
⇒ 管理人の物乞いリスト
