Nội dung bài toán

Bạn được cho ~ k ~ số nguyên tố phân biệt ~ a_1, a_2, \ldots, a_k ~ và một số nguyên ~ n ~. Nhiệm vụ của bạn là tính có bao nhiêu số nguyên từ 1 đến ~ n ~ chia hết ít nhất bởi một trong các số ~ a_1, a_2, \ldots, a_k ~.

Dữ liệu vào

• Dòng đầu tiên chứa hai số nguyên ~ n ~ và ~ k ~.
• Dòng thứ hai chứa ~ k ~ số nguyên tố ~ a_1, a_2, \ldots, a_k ~.

Dữ liệu ra

• In ra một số nguyên: số lượng các số nguyên trong đoạn ~ [1, n] ~ chia hết ít nhất bởi một số trong ~ a_1, a_2, \ldots, a_k ~.

Ràng buộc

• ~ 1 \leq n \leq 10^{18} ~
• ~ 1 \leq k \leq 20 ~
• ~ 2 \leq a_i \leq n ~

Ví dụ

Dữ liệu vào

20 2
2 5

Dữ liệu ra

12

Giải thích:

• Các số từ 1 đến 20 chia hết cho ít nhất một số trong ~ \{2, 5\} ~ là:
  • ~ 2, 4, 5, 6, 8, 10, 12, 14, 15, 16, 18, 20 ~.
• Tổng cộng có 12 số.