# [Gold III] 정수 게임 [문제 링크](https://www.acmicpc.net/problem/14848) ## 문제 설명 <p>재현이는 다음과 같은 정수 게임을 하려고 한다. 게임은 다음과 같이 이루어져 있다.</p> <ol> <li>정수 N과 크기가 K인 배열 A을 정한다.</li> <li>1부터 N까지 정수를 모두 종이에 쓴다.</li> <li>배열 A의 가장 첫 수를 고르고, 그 수를 배열에서 제거한다. 고른 수를 x라고 했을 때, 종이에 적혀있는 수 중에 x의 배수를 지운다.</li> <li>배열이 비어있을 때 까지 3번을 반복한다.</li> </ol> <p>게임이 모두 완료된 이후에, 종이에 적혀있는 수의 개수를 구하는 프로그램을 작성하시오.</p> ## 입력 <p>첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 1,000,000,000, 1 ≤ K ≤ 15)</p> <p>둘째 줄에 배열 A의 내용이 순서대로 주어진다. 배열에 담겨있는 수는 100보다 작거나 같은 자연수이다.</p> ## 출력 <p>게임이 모두 완료된 이후에, 종이에 적혀있는 수의 개수를 출력한다.</p> ## 풀이 포함 배제의 원리를 이용하여 풀었습니다. ``` c++ #include<bits/stdc++.h> using namespace std; typedef long long ll; ll n, k, a[15], cnt; 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 << n-cnt; } ```