Bội số nguyên tố

Điểm: 1,00 (OI)

Giới hạn thời gian: 1.0s

Python 3 5.0s

Giới hạn bộ nhớ: 256M

Đầu vào: stdin

Đầu ra: stdout

Tác giả:

huunguyen

Dạng bài

Ngôn ngữ cho phép

C++, Go, Java, Kotlin, Pascal, Python, Scratch

Cho số nguyên $n$ và $k$ số nguyên tố phân biệt $a_{1}, a_{2}, \dots, a_{k}$ . Đếm số lượng số nguyên trong đoạn $[1, n]$ chia hết cho ít nhất một trong $k$ số nguyên tố đã cho.

Dữ liệu vào

Dòng đầu: hai số nguyên $n$ và $k$ .
Dòng hai: $k$ số nguyên tố $a_{1}, a_{2}, \dots, a_{k}$ .

Dữ liệu ra

In một số nguyên — số lượng số nguyên trong $[1, n]$ chia hết cho ít nhất một $a_{i}$ .

Ràng buộc

$1 \leq n \leq 10^{18}$
$1 \leq k \leq 20$
$2 \leq a_{i} \leq n$ , $a_{i}$ là số nguyên tố, đôi một phân biệt

Ví dụ

Input	Output	Giải thích
20 2 2 5	12	Các số chia hết cho $2$ hoặc $5$ trong $[1, 20]$ : $2, 4, 5, 6, 8, 10, 12, 14, 15, 16, 18, 20$ .

Bình luận

Không có bình luận tại thời điểm này.