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

View as PDF

Submit solution

Points: 100
Time limit: 1.0s
Python 3 1.5s
Memory limit: 256M
Input: stdin
Output: stdout

Author:
Problem type

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ự kk 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 nm - 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
3
Note
  • Các ngày đã được lên kế hoạch là 2,\ 3,\ 4.

Comments

There are no comments at the moment.