Số Đặc Biệt

Tác giả:

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

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