백준

백준 17436 소수의 배수

콩순이냉장고 2022. 1. 27. 18:36

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

 

17436번: 소수의 배수

첫째 줄에 N(1 ≤ N ≤ 10)과 M(1 ≤ M ≤ 1012)이 주어진다. 둘째 줄에는 N개의 소수가 주어진다. 입력으로 주어지는 소수는 100보다 작거나 같으며, 같은 소수가 두 번 이상 주어지지 않는다.

www.acmicpc.net

 

문제 접근법  : 이문제를 해결하기위해

포함배제의 원리라는 이론을 알아야 합니다. 그이론을 설명하기에는 무리가 있으니 

이공식을 이용해야합니다. 

 

소수의 집합을 v[i]={입력소수들} 이라할때

 

소수가 하나일때를 생각하면 1~M 이하까지의   소수의 배수들의 개수는

 M/v[0] 입니다. 그러나

소수가 2개일때면 

N(A)= M/v[0]

N(B) = M/v[1];

이지만 N(AUB) = N(A)+N(B) - N(AnB) 가 됩니다. 

즉 소수 2,3일대

n(A) = M/2

n(B) = M/3

N(AnB) = M/6

 

입력받은 소수들은 전부 서로소이기때문에 그냥 전부 곱해줘도 상관없습니다.

따라서 위의 공식대로 소스코드를 구현하면

 

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
32
33
34
35
36
37
38
39
40
41
//By 콩순이냉장고
#include<bits/stdc++.h>
using namespace std;
#define ll long long
ll n, m;
vector<ll> v;
ll res = 0;
void input() {
    cin >> n >> m;
    v.resize(n);
    for (int i = 0; i < n; i++)
        cin >> v[i];
}
void cal(int idx,int h,int h2=0,ll mul=1) {
    if (h2 >= h) {
        ll p = h % 2 == 0 ? -1 : 1;
        res += p*(m / mul);
        return;
    }
 
    for (int i = idx; i < n; i++) {
        cal(i + 1, h, h2 + 1, mul * v[i]);
    }
}
void solve() {
    
    for (int i = 0; i < n; i++) {
        cal(0, i+1);
    }
    cout << res << "\n";
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    input();
    solve();    
}
 
 
 cs

 

 

궁금한점 혹은 모르는점 논리적인 오류등 어떤 질문이든 댓글은 언제나 환영입니다.

 

 

 

사진 출처 : https://j1w2k3.tistory.com/987