CSES - Prime Multiples | Bội số nguyên tố

Xem PDF



Tác giả:
Dạng bài
Điểm: 1700 (p) Thời gian: 1.0s Bộ nhớ: 512M Input: bàn phím Output: màn hình

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 toán có bao nhiêu trong \(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 đầu vào đầu tiên có hai số nguyên \(n\)\(k\).
  • Dòng thứ hai có \(k\) số nguyên tố \(a_1, a_2, \ldots, a_k\).

Output

In một số nguyên: số lượng số nguyên trong trong khoảng \(1, 2, \ldots, n\) chia hết cho ít nhất một trong các số nguyên tố.

Constraints

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

Example

Sample input

20 2
2 5

Sample output

12

Note

\(12\) số là \(2\), \(4\), \(5\), \(6\), \(8\), \(10\), \(12\), \(14\), \(15\), \(16\), \(18\), \(20\).


Bình luận


  • -1
    penistone 11:07 p.m. 13 Tháng 2, 2024
    Gợi ý

    Backtrack + math


    • 0
      NguyenLePhuc 6:42 p.m. 27 Tháng 11, 2023

      có cách làm nào không ạ, mình đã cày trâu bị memory


      • 0
        N7hoatt 9:25 p.m. 31 Tháng 8, 2023

        Bạn được cho \(k\) số nguyên tố phân biệt \(a_1, a_2,a_3,\dots,a_k\) và một số nguyên \(n\).

        Hãy đếm trong \(n\) số nguyên dương đầu tiên, có bao nhiêu số chia hết cho ít nhất một số trong các số nguyên tố được cho.

        Input

        • Dòng đầu tiên gồm hai số nguyên \(n\)\(k\).
        • Dòng thứ hai gồm \(k\) số nguyên tố \(a_1, a_2,a_3,\dots,a_k\).

        Output

        • In ra một số nguyên duy nhất: số lượng số trong khoảng \(1,2,\dots,n\) chia hết cho ít nhất một trong các số nguyên tố.

        Constraints

        • \(1 \leq n \leq 10^{18}\).
        • \(1 \leq k \leq 20\).
        • \(2 \leq a_i \leq n\).

        Example

        Test 1

        Input
        20 2
        2 5
        Output
        12
        Note

        Giải thích: \(12\) số bao gồm \(2,4,5,6,8,10,12,14,15,16,18,20\).


        • -3
          xthabao1 11:37 p.m. 12 Tháng 8, 2023

          chưa hiểu lắm

          1 phản hồi