Số Đặc Biệt

Xem PDF
Tất cả bài nộp
Các bài nộp tốt nhất
Xem hướng dẫn
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


  • 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[]\)

    • 0
      huanhoang2004    9:12 p.m. 8 Tháng 7, 2020 ← đã chỉnh sửa

      Anh có thể chứng minh rằng a[i]%k = a[j]%k <=> k là ước của a[i] - a[j] không ạ?


      • 1
        SPyofgame    6:04 a.m. 9 Tháng 7, 2020 ← đã chỉnh sửa

        Cách 2: \(a_i \equiv a_j \pmod k \Leftrightarrow (a_i - a_j) \equiv 0 \pmod k \Leftrightarrow (a_i - a_j) \times n = k (n \in Z)\)


        • 3
          jumptozero    9:53 p.m. 8 Tháng 7, 2020 ← đã chỉnh sửa

          @huanhoang2004, chứng mình như sau:
          Đặt \(a[i]\text{%}k=a[j]\text{%}k=t\), khi đó tồn tại các số nguyên \(m,n\) sao cho \(a[i]=mk+t,a[j]=nk+t\).

          \(\implies a[i]-a[j]=(m-n)k\implies k|(a[i]-a[j])\). Ta chứng điều phải chứng minh


        • 1
          SPyofgame    5:56 p.m. 20 Tháng 6, 2020 ← chỉnh sửa 2

          Anh có thể chia \(level\) cho \(comment\) được hông anh. Anh để ngang hàng vậy đôi khi người đọc khó hiểu anh :v


          • 2
            jumptozero    6:05 p.m. 20 Tháng 6, 2020

            Ý bạn là sao ? Mình ghi kiểu linear, nghĩ sao ghi vậy 🙂


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

              lmao :v \(linear\) this thì cũng có \(recursion\) that chứ anh

          9 bình luận nữa