Algorithm in A..Z - Inclusion–exclusion principle (포함 배제의 원리)

개념

유한 집합의 합집합의 원소의 개수를 세는 기법이다.

---

작동원리

 

 

즉 겹치는 부분이 홀수면 더하고, 겹치는 부분이 짝수이면 뺀다.

---

시간복잡도

집합의 갯수가 N일 때

O(2^N)

---

문제

www.acmicpc.net/problem/17436

17436번: 소수의 배수

---

코드

#include <bits/stdc++.h>
using namespace std;

using Int = int;
using Long = long long;

int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);

    Int n;
    Long m;
    cin >> n >> m;

    vector<Int> ve(n);
    for (auto &i : ve) {
        cin >> i;
    }

    Long ans = 0;
    for (Int bit = 1;bit < (1 << n);++bit) {
        Int count = 0;
        Long value = 1L;

        for (Int p = 0;p < n;++p) {
            if (bit & (1 << p)) {
                count++;
                value *= ve[p];
            }
        }

        if (count % 2) {
            ans += m / value;
        } else {
            ans -= m / value;
        }
    }

    cout << ans << "\n";
}