Isti ostaci svih brojeva - Rešenje

Gruba sila

Rešenje grubom silom podrazumeva da se ispitaju sve moguće vrednosti \(d\). Nijedan broj \(d\) veći od maksimalnog broja u nizu \(a\) (obeležimo ga sa \(M\)) ne može biti rešenje (tada bi ostaci bili tačno elementi niza \(a\), a to nije moguće, jer nisu svi elementi u nizu \(a\) jednaki). Dakle, proveravamo redom sve vrednosti \(d\) od \(2\) do \(M\) i za svaki linearnom pretragom proveravamo da li svi elementi niza \(a\) daju isti ostatak.

Složenost ovog algoritma je \(O(M\cdot n)\), gde je \(M\) vrednost najvećeg broja u nizu. Pošto se očekuje da se za većinu vrednosti \(d\) veoma brzo ustanovi da ne daju svi elementi isti ostatak (tj. neće biti potrebe proveravati sve elemente u nizu), na složenost dominantno utiče veličina broja \(M\).

NZD razlika brojeva

Dva broja daju isti ostatak pri deljenju sa \(d\) ako i samo ako im je apsolutna vrednost razlike deljiva sa \(d\). Dakle, svi brojevi imaju iste ostatke pri deljenju sa \(d\) ako i samo ako \(d\) deli sve razlike \(|a_i - a_j|\) za \(0 \leq i < j < n\). Da bi broj \(d\) delio sve razlike \(|a_i - a_j|\) za \(0 \leq i < j < n\), dovoljno je da deli sve razlike \(|a_0 - a_i|\), za \(0 < i < n\).

Dokažimo prethodno tvrđenje. Razmotrimo proizvoljnu razliku \(|a_i - a_j|\). Ona je jednaka ili zbiru ili razlici brojeva \(|a_0 - a_i|\) i \(|a_0 - a_j|\) (jednaka je zbiru u slučaju da je \(a_0\) između \(a_i\) i \(a_j\), a razlici u suprotnom). Međutim, ako \(d\) deli oba broja, deli i njihov zbir i njihovu razliku, pa ako \(d\) deli sve razlike prvog broja i ostalih, onda deli i razlike svih parova (naravno, ako deli razlike svih parova, onda deli i razlike između prvog broja i ostalih).

Neki broj deli sve brojeve nekog skupa ako i samo ako deli NZD elemenata tog skupa. Zato tražene vrednosti \(d\) možemo da odredimo kao sve delioce NZD-a svih razlika prvog elementa od ostalih elemenata učitanog niza \(a\).

NZD brojeva možemo lako odrediti Euklidovim algoritmom. Delioce možemo efikasno odrediti korišćenjem činjenice da se delioci javljaju u paru, tj. da svakom deliocu manjem od korena broja odgovara jedan delilac koji je veći od korena broja.

Izračunavanje razlika svih brojeva i prvog broja vrši se u složenosti \(O(n)\). Izračunavanje njihovog NZD u vremenu \(O(n \log{M})\) gde je \(M\) veličina najvećeg broja u nizu (jer je najveća apsolutna razlika sigurno manja od \(2M\)). Delioci se zatim izračunavaju u složenosti \(O(\sqrt{M})\), jer je vrednost NZD sigurno odozgo ograničena vrednošću najveće razlike.

long long NZD(long long a, long long b) {
  while (b > 0) {
    long long ost = a % b;
    a = b;
    b = ost;
  }
  return a;
}

long long NZD(const vector<long long>& a) {
  long long nzd = 0;
  for (long long x : a)
    nzd = NZD(nzd, x);
  return nzd;
}

vector<long long> Delioci(long long n) {
  vector<long long> delioci;
  long long i = 2;
  while (i * i < n) {
    if (n % i == 0) {
      delioci.push_back(i);
      delioci.push_back(n / i);
    }
    i++;
  }
  if (i * i == n)
    delioci.push_back(i);
  delioci.push_back(n);
  sort(begin(delioci), end(delioci));
  return delioci;
}

vector<long long> DeliociKojiDajuIsteOstatke(const vector<long long>& a) {
  int n = a.size();
  vector<long long> razlike(n-1);
  for (int i = 1; i < n; i++)
    razlike.push_back(abs(a[i] - a[0]));

  return Delioci(NZD(razlike));
}

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

long long NZD(long long a, long long b) {
  while (b > 0) {
    long long ost = a % b;
    a = b;
    b = ost;
  }
  return a;
}

long long NZD(const vector<long long>& a) {
  long long nzd = 0;
  for (long long x : a)
    nzd = NZD(nzd, x);
  return nzd;
}

vector<long long> Delioci(long long n) {
  vector<long long> delioci;
  long long i = 2;
  while (i * i < n) {
    if (n % i == 0) {
      delioci.push_back(i);
      delioci.push_back(n / i);
    }
    i++;
  }
  if (i * i == n)
    delioci.push_back(i);
  delioci.push_back(n);
  sort(begin(delioci), end(delioci));
  return delioci;
}

vector<long long> DeliociKojiDajuIsteOstatke(const vector<long long>& a) {
  int n = a.size();
  vector<long long> razlike(n-1);
  for (int i = 1; i < n; i++)
    razlike.push_back(abs(a[i] - a[0]));

  return Delioci(NZD(razlike));
}

int main() {
  int n;
  cin >> n;
  vector<long long> a(n);
  for (int i = 0; i < n; i++)
    cin >> a[i];

  for (long long x : DeliociKojiDajuIsteOstatke(a))
    cout << x << endl;
  
  return 0;
}