TLEOJ Contest #16 - I know what we're gonna do today

Điểm: 100

Thời gian: 1.0s

Python 3 1.5s

Bộ nhớ: 256M

Input: bàn phím

Output: màn hình

Tác giả:

_nhphuc

Dạng bài

Phineas và Ferb đang có một mùa hè tuyệt vời với số ngày là $n$ , trong mùa hè đó, Phineas và Ferb đã có dự định xây dựng một số ngày, một ngày đã được lên kế hoạch là một ngày có số thứ tự $k$ mà $k$ chia hết cho ít nhất một phần tử trong mảng số nguyên $a$ gồm $m$ phần tử cho trước.

Bạn hãy giúp Phineas và Ferb tính số ngày đã được lên kế hoạch để từ đó họ có kế hoạch để lên công việc cho những ngày còn lại nhé.

Input and Output

Input

Dòng đầu tiên gồm hai số nguyên $n$ và $m$ - số lượng ngày trong kì nghỉ của Phineas và Ferb cùng với độ dài của mảng số nguyên $a$ . $(1\leq n\leq 10^{18},\ 1\leq m\leq 18)$
Dòng thứ hai gồm $m$ số nguyên với số nguyên thứ $i$ là phần tử $a_i$ của mảng $a$ . $(1\leq a_i\leq n)$

Output

Gồm một dòng duy nhất chứa một số nguyên là kết quả của bài toán - số ngày đã được lên kế hoạch trong $n$ ngày.

Subtask

Subtask $1$ : $m\leq 3$ . ( $20\%$ số điểm)
Subtask $2$ : $n\leq 5.10^6$ . ( $20\%$ số điểm)
Subtask $3$ : Không có ràng buộc gì thêm. ( $60\%$ số điểm)

Test 1

Sample input

5 2
2 3

Sample output

Note

Các ngày đã được lên kế hoạch là $2,\ 3,\ 4$ .

Bình luận

Không có bình luận nào.