# [Gold II] 재미있는 숫자 놀이 [문제 링크](https://www.acmicpc.net/problem/12944) ## 문제 설명 <p>민호는 K개의 카드를 가지고 있는데 각각의 카드에는 양의 정수가 적혀 있다. 이 카드들을 너무 좋아하는 민호는 이것들을 이용해 재미있는 놀이를 생각해 냈다.</p> <p>1이상 N이하의 양의 정수 중에서 민호가 가지고 있는 카드들 중 적어도 한개로 나눠떨어지는 숫자는 몇개인지 알아보는 것이다.</p> <p>하지만 경우의 수가 너무 많아 손으로 셀 수 없다는 것을 깨달은 민호는 여러분들에게 도움을 요청했다. 민호를 도와 민호가 놀이를 성공적으로 마칠 수 있게 해주자.</p> ## 입력 <p>첫 번째 줄에 N, K (1 ≤ N ≤ 10⁹, 1 ≤ K ≤ 20) 이 공백을 구분으로 주어진다.</p> <p>다음 줄에는 민호가 가지고 있는 K개의 카드에 적힌 숫자가 A_i (1 ≤ i ≤ N, 1 ≤ A_i ≤ 10⁹)가 공백을 구분으로 차례대로 주어진다.</p> ## 출력 <p>1이상 N이하의 양의 정수 중 민호가 가지고 있는 카드들 중 적어도 한 개로 나눠떨어지는 수의 개수를 출력한다.</p> ## 풀이 포함 배제의 원리를 이용하여 풀었습니다. ``` c++ #include<bits/stdc++.h> using namespace std; typedef long long ll; ll n, k, cnt, a[20]; void back(int depth=0, int start=0, ll val=1) { if(val>n) return; if(depth) { if(depth%2) cnt += n/val; else cnt -= n/val; } for(int i=start;i<k;i++) back(depth+1, i+1, lcm(val, a[i])); } int main() { ios::sync_with_stdio(0); cin.tie(0); cin >> n >> k; for(int i=0;i<k;i++) cin >> a[i]; back(); cout << cnt; } ```