Chia hết cho số nguyên tố

Time limit: 1.0s , Memory limit: 256M , Points: 10 (partial)

Cho trước $k$ ~k~ số nguyên tố phân biệt $a_1, a_2, \ldots, a_k$ ~a_1, a_2, \ldots, a_k~ và một số nguyên $N$ ~N~. Lập trình tính xem có bao nhiêu trong $N$ ~N~ số nguyên dương đầu tiên chia hết cho ít nhất một trong các số nguyên tố đã cho.

Input

Dòng thứ nhất chứa hai số nguyên $N, k$ ~N, k~ thỏa $1\le N \le 10^{18}, 1 \le k \le 20$ ~1\le N \le 10^{18}, 1 \le k \le 20~.

Dòng tiếp theo chứa $k$ ~k~ số nguyên tố phân biệt $a_i$ ~a_i~ thỏa $1 \le a_i \le N$ ~1 \le a_i \le N~.

Output

In ra kết quả cần tính.

Samples

Sample Input 1

20 2
2 5

Sample Output 1

Note

Có $12$ ~12~ số là 2, 4, 5, 6, 8, 10, 12, 14, 15, 16, 18, 20.

Comments

0

ndmccoder232 commented on March 2, 2024, 2:52 p.m.

là sao k hiểu

Link

0

Kuro_Neko commented on March 2, 2024, 3:13 p.m.

bài này cho trước một số nguyên n và một số nguyên k (là số lượng số nguyên tố), nhiệm vụ của bạn là đếm xem từ 2 đến n có bao nhiêu số chia hết cho k số nguyên tố từ dòng thứ 2, với điều kiện là những số đó chỉ đếm được một lần, ví dụ 10 chia hết cho cả 2 và 5, nhưng chỉ được tính một lần(+1 thay vì +2) vào đáp án

Link