[BOJ] 17436 - 소수의 배수

문제 : https://www.acmicpc.net/problem/17436

---

[알고리즘풀이]

N개의 소수를 p1, p2, ⋯ pn 이라고 하자.

그리고 1 ~ M 이하의 자연수 중에서 p1으로 나눠지는 수들의 집합을 P1, ⋯ pn으로 나눠지는 수들의 집합을 Pn 이라고 한다면, 우리가 구하고 싶은 답은 n(P1 U P2 U ⋯ U Pn)이 될 것이다. ( 합집합의 원소의 개수 )

n(P1 U P2 U ⋯ U Pn)

=+n(P1) + n(P2) + ⋯ + n(Pn)

  -n(P1 ∩ P2) -n(P1 ∩ P3) - ⋯ - n(Pn-1 ∩ Pn)

  +n(P1 ∩ P2 ∩ P3) + ⋯ + n(Pn-2 ∩ Pn-1 ∩ Pn)

  - ⋯

  (-1)^(n-1) * n(P1 ∩ P2 ∩ ⋯ ∩Pn)

이고 모두 소수이므로 서로소 성질에 의해 n(Pi ∩ Pj) = M / (Pi * Pj) 가 성립한다.

따라서, 백트레킹 기법을 활용해 위의 공식을 계산해주면 된다.

#include<iostream>
#include<vector>

using namespace std;

long long answer, m;
int n, p[10];

void bt(int, int, int, vector<int>);

int main(void){
	cin >> n >> m;
    for(int i = 0; i < n; i++){
        cin >> p[i];
    }
    for (int i = 1; i <= n; i++){
        // i 개씩 뽑을거야. 안겹치게 오름차순으로
        for(int j = 1; j <= n; j++){
            vector<int> v;
            v.push_back(j);
            bt(1, j, i, v);
            v.pop_back();
        }
    }
    cout << answer;
}

void bt(int size, int start, int l, vector<int> v){
    if(size == l){
    	if(l % 2 == 1){
            long long temp = 1;
            for(int i = 0; i < l ; i++){
                temp *= p[v[i] - 1];
            }
            answer += m / temp;
        }
        else{
            long long temp = 1;
            for(int i =0; i < l; i++)
                temp *= p[v[i] - 1];
            answer -= m / temp;
        }
        return;
    }
    for(int i = start + 1; i <= n; i++){
        v.push_back(i);
        bt(size + 1,i,l,v);
        v.pop_back();
    }
}

---