# [Gold I] 나누어 질까 [문제 링크](https://www.acmicpc.net/problem/1441) ## 문제 설명 <p>어떤 숫자 배열 A가 주어지면, L보다 크거나 같고, R보다 작거나 같은 자연수 중에, A에 속해있는 원소 중 적어도 하나로 나누어지는 수의 개수를 구하는 프로그램을 작성하시오.</p> ## 입력 <p>첫째 줄에 A의 크기 N과 L, R이 주어진다. N은 18보다 작거나 같은 자연수이고, L은 1,000,000,000보다 작거나 같은 자연수, R은 L보다 크거나 같고, 1,000,000,000보다 작거나 같은 자연수이다. 둘째 줄에 A에 속하는 원소가 들어온다. 각 원소는 공백을 사이에 두고 구분되어 있고, 원소는 1,000,000,000보다 작거나 같은 자연수이다.</p> ## 출력 <p>첫째 줄에 L보다 크거나 같고, R보다 작거나 같은 자연수 중에, A에 속해있는 원소 중 적어도 하나로 나누어지는 수의 개수를 출력한다.</p> ## 풀이 포함 배제의 원리를 이용하여 풀었습니다. ``` c++ #include<bits/stdc++.h> using namespace std; typedef long long ll; ll n, l, r, cnt, a[18]; void back(int depth=0, int start=0, ll val=1) { if(val>r) return; if(depth) { if(depth%2) cnt += r/val - (l-1)/val; else cnt -= r/val - (l-1)/val; } for(int i=start;i<n;i++) back(depth+1, i+1, lcm(val, a[i])); } int main() { ios::sync_with_stdio(0); cin.tie(0); cin >> n >> l >> r; for(int i=0;i<n;i++) cin >> a[i]; back(); cout << cnt; } ```