Tập GCD

Xem PDF
Tác giả:
CaiWinDao
Dạng bài
Ngôn ngữ cho phép
C#, C++, Clang, Clang++, Cobol, D, Groovy, Haskell, Java, JS, Kotlin, Lua, Node JS, ObjectiveC, OCaml, Output, Pascal, PHP, Prolog, Pypy, Pypy 3, Python, Ruby, Rust, Scala, Scratch, Swift
Điểm: 300 (p) Thời gian: 0.5s Bộ nhớ: 256M Input: bàn phím Output: màn hình

Một hôm, Đức nghĩ ra một cách xây dựng một tập hợp số nguyên dương, gọi là \(S\), rồi đố Hân xác định xem một số nguyên dương \(K\) bất kỳ có thuộc tập \(S\) hay không. Biết rằng tập \(S\) của Đức chỉ gồm các số xác định theo hai quy tắc:

  • Quy tắc 1: Các số \(a_1\), \(a_2\),..., \(a_n\) thuộc \(S\).
  • Quy tắc 2: Nếu \(a\) và \(b\) thuộc \(S\) thì ước số chung lớn nhất của \(a\) và \(b\) cũng thuộc \(S\).
    Vì số phần tử của tập S có thể rất lớn nên Hân đành phải nhờ bạn lập trình tính toán giúp để trả lời câu hỏi của Đức. Bạn hãy giúp Hân nhé!

Input

  • Dòng đầu chứa số nguyên dương \(T\) thể hiện số câu hỏi.
  • Mỗi nhóm trong \(T\) nhóm dòng tiếp theo mô tả một câu hỏi, gồm:
  • Dòng đầu chứa hai số nguyên dương \(n\) và \(K\).
  • Dòng tiếp theo chứa \(n\) số nguyên dương phân biệt \(a_1\), \(a_2\),..., \(a_n\).

Output

  • Gồm \(T\) dòng, mỗi dòng in ra YES nếu \(K\) nằm trong tập \(S\) tương ứng, hoặc in ra NO trong trường hợp ngược lại.

Constraints

  • \(T\leq 5\)
  • \(n\leq 20000, a_i\leq 10^{12}, K\leq 10^{12}\)

Scoring

  • Subtask \(1\) (\(30\%\) số điểm): \(n\leq 20, a_i\leq 10^6, K\leq 10^6\).
  • Subtask \(2\) (\(30\%\) số điểm): \(n\leq 20000, a_i\leq 10^6, K\leq 10^6\).
  • Subtask \(3\) (\(40\%\) số điểm): Không có ràng buộc gì thêm

Example

Test 1

Input 
2
5 4
24 2 60 6 40
2 3
9 10
Output 
YES
NO

Bình luận


  • 0
    SPyofgame    6:50 p.m. 14 Tháng 6, 2020 ← chỉnh sửa 12

    Editorial Teleportation


    • 15
      cuom1999    1:08 a.m. 15 Tháng 6, 2020

      Một cách code đơn giản hơn là lấy gcd của tất cả bội của k. Nếu nó bằng k thì YES, ngược lại thì NO


      • 0
        CQTshadow    10:01 a.m. 15 Tháng 6, 2020

        Chứng minh toán học của cách này là sao ạ ?


        • 1
          cuom1999    10:45 a.m. 15 Tháng 6, 2020

          Hoặc có thể chứng minh như thế này. Theo lời giải trên, ta không cần quan tâm đến các số không chia hết cho \(k\), vì nếu dùng các số này thì kết quả không thể chia hết cho \(k\) nữa. Đồng thời, trong các số còn lại (bội của \(k\)), số nhỏ nhất có thể tạo được chính là \(\gcd\) của chúng. Vì vậy nếu số này khác \(k\) thì các số tạo được luôn lớn hơn \(k\).


          • 0
            tuanlinh    9:09 p.m. 30 Tháng 6, 2020

            em làm theo cách anh nhưng bị WA


            • 0
              SPyofgame    9:15 p.m. 30 Tháng 6, 2020

              Lời giải đó là cái code cuối cùng trong phần editorial ấy anh :v


              • 0
                tuanlinh    9:24 p.m. 30 Tháng 6, 2020

                chỗ if (x % k == 0) res = gcd(res, x / k); với x=20, k=res=4 thì res=1


                • 0
                  SPyofgame    10:37 p.m. 30 Tháng 6, 2020

                  Lúc đầu mình có khởi tạo \(res = k * k\) mà thấy \(n \geq 2\) không cần nên để vậy mà lại quên if else luôn haha

                  Mình cập nhật lời giải rồi đó


                  • 0
                    tuanlinh    10:52 a.m. 1 Tháng 7, 2020

                    giờ mình mới hiểu lời giải :v
                    có góp ý trong code cuối nên cho res=0 thay vì res=k thì đúng hơn


                    • 0
                      SPyofgame    11:06 a.m. 1 Tháng 7, 2020 ← đã chỉnh sửa

                      :V bữa mình lag kiểu gì tính \(gcd(0, k) \neq k\) nên mình tính đặt \(n = k ^ 2\) á

                      Cảm ơn bạn, đã update editorial


                • 0
                  tuanlinh    9:22 p.m. 30 Tháng 6, 2020

                  giả sử với n=1, k=4, a1=20 thì theo code đó có phải ra YES k


              • 0
                NguyenHuuNhatQuang    5:12 p.m. 20 Tháng 6, 2020

                Cách của anh có 1 lỗi. Ví dụ test sau:

                k=2

                Các số trong mảng là: 30, 70 và 42

                Thì ƯCLN của 3 số đó là 2 (=k).

                Nhưng nếu lấy 2 số bất kì trong 3 số đó thì không thể tạo ra số 2 được:

                • 30 70 ra 10

                • 30 42 ra 6

                • 70 42 ra 14

                Đây là lỗi trong cách làm của anh.


                • 0
                  SPyofgame    5:20 p.m. 20 Tháng 6, 2020

                  Có gcd(gcd(30, 70), gcd(30, 42)) = gcd(10, 6) = 2 mà ạ ?


            • 0
              SPyofgame    10:07 a.m. 15 Tháng 6, 2020 ← đã chỉnh sửa

              Cách của em nếu có các số \((a, b, c, ...)\) là bội k

              thì em sẽ tạo ra các \(gcd(a, b)\), \(gcd(a, c)\), ... \(gcd(b, c)\), ...

              rồi lại tạo \(gcd(gcd(a, b), a)\), \(gcd(gcd(a, b), b)\), \(gcd(gcd(a, b), c)\), ... \(gcd(gcd(a, c), a)\), \(gcd(gcd(a, c), b)\), \(gcd(gcd(a, c), c)\), ... \(gcd(gcd(b, c), a)\), \(gcd(gcd(b, c), b)\), \(gcd(gcd(b, c), c)\)...

              nhưng vì trong \(set\) \(S\) mình chỉ quan tâm tới các phần tử phân biệt nên là mình loại bớt các ước vô nghĩa. Cuối cùng còn lại \(gcd(a, b, c, ...)\)

          3 bình luận nữa