Số Đặc Biệt

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

Khôi có một mảng số tự nhiên \(A\) có \(N\) phần tử. Anh ấy phải tìm ra tất cả các số đặc biệt \(K\).

Biết rằng số đặc biệt \(K\) phải thỏa mãn những điều sau:

1) K>1

2) A[1]%K = A[2]%K = A[3]%K = ... = A[N]%K

Hãy giúp Khôi tìm ra tất cả các số đặc biệt \(K\).

Input

  • Dòng đầu tiên chứa \(1\) số nguyên dương \(N (2 ≤ N ≤ 10^5)\)
  • Gồm \(N\) dòng, dòng \(i\) chứa giá trị của \(A_i (1 ≤ A_i ≤ 10^9)\)
  • Các số trong mảng \(A\) khác nhau đôi một
    Dữ liệu Input đảm bảo có ít nhất \(1\) số \(K\) thỏa mãn và nhiều nhất 106106 số \(K\) thỏa mãn

Output

  • Tất cả các số đăc biệt K theo thứ tự tăng dần. (Mỗi số trên 1 dòng)

Example

Test 1

Input 
3
38
6
34
Output 
2
4

Bình luận


  • 0
    huyhau6a2    7:47 a.m. 30 Tháng 12, 2021 ← đã chỉnh sửa

    (đã thu hồi do hiểu rồi)


    • 1
      longkold00    9:40 a.m. 21 Tháng 10, 2021

      Đề bài 2 số khác nhau đôi một nhưng vẫn tồn tại 2 ptu = nhau là sao nhỉ, ai thông não mình với :>

      1 phản hồi

      • 0
        VoBaThongL921    10:16 a.m. 19 Tháng 10, 2021

        Nhiều ông chép code y hệt anh jumptozero luôn ạ :v


        • 0
          hoangkhoa20000006    5:36 p.m. 11 Tháng 7, 2021

          std::bad_alloc là lỗi gì vậy ạ :))

          2 phản hồi

          • 0
            ekhoavvdd    1:38 p.m. 8 Tháng 6, 2021

            compiler timed out (> 10 seconds) là lỗi gì vậy mọi người 😃 ?


            • 4
              jumptozero    5:51 p.m. 20 Tháng 6, 2020
              • Mình xin chia sẻ lời giải bài này như sau:
              • Ta có: \(A[i]\text{%} K = A[j]\text{%} K \iff K| (A[i]-A[j])\) (Ghi chú: \(a|b\): Có nghĩa là \(a\) là ước của \(b\)).
              • Do đó để thõa mãn yêu cầu bài toán, \(K\) phải là ước chung của tất cả \(|A[i]-A[j]|(\forall 1\le i\ne j\le n)\)
              • Từ đây suy ra \(K\) là ước của \(Min\left\{|A[i]-A[j]|\right\}(\forall 1\le i\ne j\le n)\).
              • Mục đích của việc này là để mình thu hẹp số lượng \(K\) cần tìm.
              • Vì đề bài đã cho là các \(A[i],A[j]\) khác nhau từng đôi một nên ở đây chúng ta sẽ không cần quan tâm đến trường hợp tất cả các phần tử của mảng \(A[]\) bằng nhau. (Vì nếu trường hợp này xảy ra thì sẽ có vô số \(K\) cần tìm (vì \(K|0\))).
              • Đến đây mình code như sau:
              • Đầu tiên ta sort lại mảng \(A[]\) theo thứ tự tăng dần, tiếp theo xây dựng mảng \(B\) thỏa mãn \(B[i]=A[i+1]-A[i]\) (mảng \(B[]\) có \(n-1\) phần tử)
              • Gọi \(T=Min\left\{B[i]\right\}(\forall 1\le i\le n-1)\). Khi đó \(K|T\)
              • Gọi \(S_T\) là tập hợp các ước của \(T\). Khi đó \(K\in S_T\)
              • Đến đây ta chỉ cần cho hai vòng for để duyệt kiểm tra xem mỗi phần tử thuộc \(S_T\) có là ước của tất cả các phần tử của mảng \(B[]\) hay không ? Nếu có thì thêm phần tử đó vào mảng \(Res\).
              • Khi đó mảng \(Res\) là tập hợp của những số \(K\) cần tìm.
              • Các bạn có thể tham khảo code mình tại \(\href{https://ideone.com/TKdaAu}{đây}\)
              • Nếu có gì sai hoặc khó hiểu, mọi người cứ comment $
              • P/s: Ở đây đề bài có thể mở rộng là: Các số \(A[i]\) không đồng thời bằng nhau, thì bài toán vẫn có thể giải quyết !
              • P/s: Ở bài này mình dùng set để unique các phần tử của mảng \(A[]\)
              2 phản hồi

              • 0
                jumptozero    6:52 a.m. 20 Tháng 6, 2020 ← chỉnh sửa 3

                compiler timed out (> 10 seconds) là lỗi gì mọi người !

                2 phản hồi

                • 0
                  vinhntndu    10:21 p.m. 19 Tháng 6, 2020

                  N=100 để 3 for?

                  1 phản hồi

                  • 0
                    algorit    9:52 p.m. 19 Tháng 6, 2020 ← đã chỉnh sửa

                    AD ơi , nâng lên 10^5 đi ạ

                    1 phản hồi

                    • 0
                      SPyofgame    8:26 p.m. 19 Tháng 6, 2020 ← đã chỉnh sửa

                      Nếu \(A_i = A_j \forall (1 \leq i \leq j \leq n)\) thì số lượng K là vô hạn :v

                      1 phản hồi