Editorial for Số Đặc Biệt

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.

Submitting an official solution before solving the problem yourself is a bannable offence.
  • 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[]$

Comments

There are no comments at the moment.