7109 : 포함배제 원리
•시간제한: 2.000 S
•메모리제한: 256 MB
•제출: 0
•통과: 0
•만든사람: suakii
문제 설명
1부터 N까지의 자연수 중에서 주어진 K개의 자연수들 중 적어도 하나의 배수인 수의 개수를 구하는 프로그램을 작성하십시오.
[제약 조건]
• 각 자연수는 100 이하의 자연수입니다.
[제약 조건]
• 각 자연수는 100 이하의 자연수입니다.
입력 설명
첫째 줄에 자연수 N과 자연수의 개수 K가 공백으로 구분되어 주어집니다. (1 ≤ N ≤ 10^9, 1 ≤ K ≤ 4)
둘째 줄에 K개의 서로 다른 자연수가 공백으로 구분되어 주어집니다. 각 자연수는 100 이하입니다.
둘째 줄에 K개의 서로 다른 자연수가 공백으로 구분되어 주어집니다. 각 자연수는 100 이하입니다.
출력 설명
1부터 N까지의 수 중 K개 소수 중 적어도 하나의 배수인 수의 개수를 출력합니다.
입력 예시
COPY
복사되었습니다!
복사되었습니다!
100 3
2 3 5
출력 예시
COPY
복사되었습니다!
복사되었습니다!
74도움
포함배제 원리(Principle of Inclusion-Exclusion)를 이용합니다. K개 자연수들의 부분집합에 대해 최소공배수(LCM)를 구하여, 홀수 개를 고른 경우 N // LCM을 더하고, 짝수 개를 고른 경우 뺍니다.