Informatica Online Judge

  수학 공부2 [0818 / 0332]

Time Limit(Test case) : 1000(ms)
Number of users who solved : 42   Total Tried : 110


The Champion of this Problem (C++) : gst19076 - 0ms / 585byte
My Best Submission (C++) : N/A

[]

Background

이번에 다시 수학공부를 하려고 한다.



다음과 같이 m개의 원소를 가진 집합이 있다.

S = { s1, s2, ... sm }

1이상 n이하의 자연수를 집합 S의 각 원소들로 나눌때 적어도 하나의 원소 이상으로 나누어 떨어지는 값들의 개수를 구하는 프로그램을 작성하시오.

만약 n = 10 이고 집합이 {2, 3}이라면

1은 2, 3으로 나눠떨어지지 않음.
2는 2로 나눠떨어짐.
3은 3으로 나눠떨어짐.
4는 2로 나눠떨어지고,
5는 2, 3으로 나눠떨어지지 않음.
6은 2, 3모두 나눠떨어짐
7은 아무 값으로도 나눠떨어지지 않음.
8은 2로 나눠떨어지고,
9는 3으로 나눠떨어지며,
10은 2로 나눠떨어지므로

모두 7개의 값들이 2, 3으로 나눠떨어진다. 따라서 답은 7이 된다.

Input

첫 번째 줄에 n, m이 공백으로 구분되어 입력된다.
두 번째 줄에 m개의 원소가 공백으로 구분되어 입력된다.

단, 1 <= n <= 1,000,000,000, 1 <= m <= 15, 각 원소의 값은 n이하의 값을 가진다.

Output

나눠떨어지는 값의 개수를 출력한다.

IO Example

입력
10 2
2 3

출력
7

입력2
100 3
2 3 7

출력
72

Submit : [C/C++] | [C++11] | [Obj-C] | [Java] | [Python]
Prob Analysis : [Problem Statistics] | [Solution]