Metoda włączeń i wyłączeń cz II.

Przedstawię dwa proste zadania, które można rozwiązać za pomocą metody włączeń i wyłączeń.

Mamy danych 10 prostopadłościanów ortogonalnych (to znaczy takich, których krawędzie są równoległe do osi układów współrzędnych). Prostopadłościany te mogą na siebie nachodzić. Pytamy o sumę objętości tych prostopadłościanów.
Prostopadłościan ortogonalny może być zapisany za pomocą pary punktów: lewego, dolnego, "bliższego" (nam) oraz prawego, górnego, "dalszego". Powiedzmy, że pewien prostopadłościan jest określony za pomocą pary: (a₁, a₂, a₃) oraz (b₁, b₂, b₃). Jego objętość można wyrazić wzorem: (b₁-a₁)(b₂-a₂)(b₃-a₃).
Bardzo łatwo także wyznaczyć przecięcie dwóch prostopadłościanów, które także jest prostopadłościanem. Jeśli pierwszy z prostopadłościanów to (a₁, a₂, a₃) oraz (b₁, b₂, b₃), a drugi: (c₁, c₂, c₃) oraz (d₁, d₂, d₃) to prostopadłościan, który jest ich przecięciem to: (max{a₁, c₁}, max{a₂, c₂}, max{a₃, c₃}) oraz (min{b₁,d₁}, min{b₂,d₂}, min{b₃,d₃}).
Tak jak nauczyliśmy się w poprzedniej części - możemy teraz obliczyć sumę objętości prostopadłościanów na podstawię ich przecięć.

Drugie zadanie jest następujące. Mamy dany zbiór S = {1, 2, 3, ..., 10⁹}. Pytamy ile jest liczb w tym zbiorze, które są podzielne przez 9, 11 lub 15?
Oznaczmy przez D_k zbiór tych wszystkich liczb należących do S, które są podzielne przez k. Nie trudno zauważyć, że |D_k| = 10⁹ / k. Przy czym dzielenie tutaj rozumiemy jako dzielenie całkowitoliczbowe.
Tak samo łatwo można policzyć przecięcie dwóch zbiorów. Wystarczy tylko zauważyć, że:
Gdzie lcm(k, l) oznacza najmniejszą wspólną wielokrotność liczb k oraz l.
Zgodnie z opisaną w poprzedniej części metodą włączeń i wyłączeń możemy obliczyć sumę zdefiniowanych wzorów.

Dobrym ćwiczeniem będzie dla każdego implementacja powyższych algorytmów. Nie powinno to nikomu sprawić większych problemów, ale warto się oswoić z tą techniką.