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

View as PDF
All submissions
Best submissions
Authors:
kitsune , Only_Avocado
Problem types
Points: 1700 (p) Time limit: 1.0s Memory limit: 512M Input: stdin Output: stdout

You are given \(k\) distinct prime numbers \(a_1,a_2,\dots,a_k\) and an integer \(n\).

Your task is to calculate how many of the first \(n\) positive integers are divisible by at least one of the given prime numbers.

Input

  • The first input line has two integers \(n\) and \(k\).
  • The second line has \(k\) prime numbers \(a_1,a_2,\dots,a_k\).

Output

  • Print one integer: the number integers within the interval \(1,2,\dots,n\) that are divisible by at least one of the prime numbers.

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

The \(12\) numbers are \(2,4,5,6,8,10,12,14,15,16,18,20\)

Comments


  • 0
    HoangTung    8:48 a.m. 22 sep, 2024

    cs ai AC chx giúp tôi với


    • 1
      tienminhho509    12:34 p.m. 9 sep, 2024

      ai cho e xin code đc ko ạ


      • -4
        penistone    11:07 p.m. 13 feb, 2024
        Gợi ý

        Backtrack + math


        • 0
          NguyenLePhuc    6:42 p.m. 27 nov, 2023

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


          • 1
            N7hoatt    9:25 p.m. 31 aug, 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\) và \(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\).


            • -4
              xthabao1    11:37 p.m. 12 aug, 2023

              chưa hiểu lắm

              1 reply