Hướng dẫn cho Số Đặc Biệt

Chỉ sử dụng khi thực sự cần thiết như một cách tôn trọng tác giả và người viết hướng dẫn này.

Chép code từ bài hướng dẫn để nộp bài là hành vi có thể dẫn đến khóa tài khoản.

Authors: jumptozero

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 đây

$$$ #include<bits/stdc++.h> using namespace std; #define ll long long #define maxn (ll)(1e5+5) ll a[maxn],i,n,res,tmp,b[maxn],aka,dau,dem; vector<ll> v; set<ll> s,lope; set<ll>::iterator it; int main(){ cin>>n; for(i=0;i<n;i++) {cin>>a[i];lope.insert(a[i]);} //cout<<lope.size()<<'\n'; n=lope.size(); for(it=lope.begin();it!=lope.end();it++){ a[dem++]=*it; } //for(i=0;i<n;i++) cout<<a[i]<<" "; sort(a,a+n); for(i=0;i<n-1;i++) b[i]=a[i+1]-a[i]; sort(b,b+n-1); for(i=0;i<n-1;i++) if(b[i]!=0){tmp=b[i];break;} for(i=1;i*i<=tmp;i++){ if(tmp%i==0) {s.insert(i);s.insert(tmp/i);} } for(it=s.begin();it!=s.end();it++){ aka = *it; dau=0; if(aka==1) continue; for(i=0;i<n-1;i++){ if(b[i]%aka){dau=1;break;} } if(dau==0) v.push_back(aka); } for(i=0;i<v.size();i++) cout<<v[i]<<'\n'; return 0; } $$$ </details> + 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[]$

Bình luận

Không có bình luận nào.