시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 | 512 MB | 392 | 161 | 109 | 39.350% |
민호는 K개의 카드를 가지고 있는데 각각의 카드에는 양의 정수가 적혀 있다. 이 카드들을 너무 좋아하는 민호는 이것들을 이용해 재미있는 놀이를 생각해 냈다.
1이상 N이하의 양의 정수 중에서 민호가 가지고 있는 카드들 중 적어도 한개로 나눠떨어지는 숫자는 몇개인지 알아보는 것이다.
하지만 경우의 수가 너무 많아 손으로 셀 수 없다는 것을 깨달은 민호는 여러분들에게 도움을 요청했다. 민호를 도와 민호가 놀이를 성공적으로 마칠 수 있게 해주자.
첫 번째 줄에 N, K (1 ≤ N ≤ 109, 1 ≤ K ≤ 20) 이 공백을 구분으로 주어진다.
다음 줄에는 민호가 가지고 있는 K개의 카드에 적힌 숫자가 Ai (1 ≤ i ≤ N, 1 ≤ Ai ≤ 109)가 공백을 구분으로 차례대로 주어진다.
1이상 N이하의 양의 정수 중 민호가 가지고 있는 카드들 중 적어도 한 개로 나눠떨어지는 수의 개수를 출력한다.
100 2 2 3
67
100 3 2 3 7
72