BOJ 17436 : 소수의 배수

• 문제 링크 : boj.kr/17436
• 난이도 : G3
• 태그 : 조합론

---

코드

#include <bits/stdc++.h>

#define all(x) (x).begin(), (x).end()

#define INF 0x7FFFFFFF

using namespace std;

using ll = long long;
using ld = long double;
using pii = pair<int,int>;
using pll = pair<ll, ll>;

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

    ll n, m;
    cin >> n >> m;
    ll ans = 0;
    vector<ll> arr(n);
    for(auto &u : arr) cin >> u;
    for(int i = 1; i < 1 << n; i++) {
        ll total = 1;
        int cnt = 0;
        for(int j = 0; j < n; j++) {
            if(i & (1 << j)) {
                total *= arr[j];
                cnt++;
            }
        }
        ans += (cnt % 2 ? 1 : -1) * (m / total);
    }
    cout << ans;

    return 0;
}

---

풀이

m을 어떤 수로 나누어 그 수의 배수의 개수를 구할 수 있다.

어떤 수는 주어진 소수를 곱하거나 곱하지 않아 얻을 수 있다.

포함 배제의 원리에 의해 어떤 수에 소수가 홀수번 곱해졌으면 결과에 더해주고, 짝수번 곱해졌으면 결과에 빼준다.