Груба сила

Решење грубом силом подразумева да линеарном претрагом пронађемо најмањи број који при дељењу са датим делиоцима даје дате остатке.

#include <iostream>
#include <vector>

using namespace std;
 
int main(void) {
  // ucitavamo ulazne podatke
  long long a[3], n[3];
  for (int i = 0; i < 3; i++)
    cin >> a[i] >> n[i];

  // rezultat izracunavamo na osnovu kineske teoreme o ostacima
  for (long long rezultat = 0; true; rezultat++)
    if (rezultat % n[0] == a[0] &&
        rezultat % n[1] == a[1] &&
        rezultat % n[2] == a[2]) {
      cout << rezultat << endl;
      break;
    }

  return 0;
}

Сито

Постоји један поступак који није превише математички захтеван, али који није оптималан у смислу ефикасности (но, испоставља се да је довољно ефикасан да реши задатак у оквиру постављених ограничења). Приступ је заснован на паметној претрази. Ако број \(r\) са бројем \(n_1\) даје остатак \(a_1\) онда је он сигурно један од чланова аритметичког низа \(a_1\), \(a_1 + n_1\), \(a_1 + 2n_1\), … У петљи редом проверавамо ове бројеве све док не наиђемо на први елемент који при дељењу са \(n_2\) даје остатак \(a_2\). Када такав број \(a_{12}\) нађемо (он ће бити најмањи позитиван број са особином да при дељењу са \(n_1\) и \(n_2\) даје редом остатке \(a_1\) и \(a_2\)), знамо да ће сваки наредни број који задовољава то својство бити члан аритметичког низа \(a_{12}\), \(a_{12} + n_1\cdot n_2\), \(a_{12} + 2\cdot n_1\cdot n_2\), … Редом претражујемо елементе овог низа док не наиђемо на елемент \(a_{123}\) који при дељењу са \(n_3\) даје остатак \(a_3\). Пошто су у нашем задатку дата само три елемента, ово је и коначно решење. Поступак би се лако уопштио тако што би се након проналажења \(a_{123}\) посматрали бројеви \(a_{123}\), \(a_{123} + n_1\cdot n_2 \cdot n_3\), \(a_{123} + 2\cdot n_1\cdot n_2 \cdot n_3\) и тако даље.

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

using namespace std;

int main() {
  // ucitavamo delioce i ostatke
  int k = 3;
  vector<long long> a(k), n(k);
  for (int i = 0; i < k; i++)
    cin >> a[i] >> n[i];

  // sortiramo nizove opadajuce po n - nizovi su kratki pa koristimo
  // naivnu implementaciju selection sort algoritma
  for (int i = 0; i < k; i++)
    for (int j = i+1; j < k; j++)
      if (n[i] > n[j]) {
        swap(n[i], n[j]);
        swap(a[i], a[j]);
      }

  // "sito"
  long long m = a[0], p = n[0];
  for (int i = 1; i < k; i++) {
    while (m % n[i] != a[i])
      m += p;
    p *= n[i];
  }

  // prijavljujemo rezultat
  cout << m << endl;
  
  return 0;
}

Кинеска теорема о остацима

Иако се у задатку посматрају тачно три делиоца и остатка, размотримо мало општији случај проналажења броја \(r\) такво да за \(k\) узајамно простих бројева \(n_1, \ldots, n_k\) важи да је \(r\,\mathrm{mod}\,n_1 = a_1\), \(\ldots\), \(r\,\mathrm{mod}\,n_k = a_k\). Сличан проблем решавања система конруенција посматран је још у древној Кини, тако да је поступак решавања који ћемо описати и применити у решењу заснован на тврђењу које се назива кинеска теорема о остацима. Она тврди да ако је \(N = n_1 \ldots n_k\) производ свих бројева \(n_i\) и ако су бројеви \(n_1, \ldots, n_k\) међусобно, у паровима, узајамно прости, тада задати систем услова има јединствено решење \(r\) такво да је \(0 \leq r < N\).

Ако за свако \(i\) такво да је \(1 \leq i \leq k\) пронађемо број \(r_i\) такав да при дељењу са бројем \(n_i\) даје остатак \(a_i\) док при дељењу са свим другим бројевима \(n_j\) за \(1 \leq j \leq k\) и \(j \neq i\) даје остатак 0, тада ће тражени резултат \(r\) бити једнак збиру свих бројева \(r_i\) по модулу \(N\) тј. важиће да је \(r = r_1 +_N \ldots +_N r_k\), односно \(r = (r_1 + \ldots + r_k)\,\mathrm{mod}\,N\).

Размотримо сада проблем одређивања вредности \(r_i\). Ако је број \(r_i\) дељив са свим коефицијентима \(n_j\) осим евентуално са \(n_i\) он је дељив и са \(p_i = N/n_i\) тј. мора да представља неки умножак броја \(p_i\) тј. мора бити облика \(c_i \cdot p_i\), за неки коефицијент \(c_i\). Да би \(r_i\) при дељењу са \(n_i\) дао остатак \(a_i\) желимо да важи да је \(c_i \cdot_{n_i} p_i = a_i\). Одавде се намеће да се \(c_i\) може добити неким обликом дељења по модулу \(n_i\) броја \(a_i\) бројем \(p_i\). Разматрајмо модуларни инверз \(p_i^{-1}\) броја \(p_i\) по модулу \(n_i\), тј. број \(p_i^{-1}\) такав да је \((p_i^{-1} \cdot p_i) \,\mathrm{mod}\,n_i = 1\) (проналажење модуларног инверза описали смо у задатку [modularni_inverz]). Модуларни инверз ће постојати јер су бројеви \(p_i\) и \(n_i\) узајамно прости. Нека је \(c_i = a_i \cdot_N p_i^{-1}\). Тада је тражени број \(r_i\) производ по модулу \(N\) бројева \(a_i\), \(p_i^{-1}\) и \(p_i\) тј. број \(r_i = (a_i \cdot_N p_i^{-1})\cdot_N p_i\) има тражена својства.

С обзиром на то да међурезултати могу бити велики бројеви, треба бити веома обазрив на могућност прекорачења. Узевши у обзир ограничења дата у тексту задатка (да су задата само три делиоца и три остатка, као и да су сви бројеви \(n_i\) ограничени одозго са \(10^5\)), у имплементацији може да се користи 64-битни тип за запис целих бројева који може да чува вредности до \(10^{18}\) (али и то само ако се формуле додатно мало трансформишу). Наиме, бројеви \(n_i\) имају ограничење \(10^5\) тако да њихов производ \(n_1\cdot n_2\cdot n_3\) има ограничење \(10^{15}\) и за његову репрезентацију никако нису довољна 32 бита, али јесте довољно 64 бита. Бројеви \(p_i\) имају горње ограничење \(10^{10}\), док њихов инверз по модулу \(n_i\) и број \(a_i\) имају горње ограничење \(10^5\), тако да би директно израчунавање производа \(a_i\cdot p_i^{-1}\cdot p_i\) проузроковало прекорачење 64-битног типа података. Чак и израчунавања остатка при дељењу са \(N\) пре и након сваке операције нас не би заштитило од прекорачења. Вредност \((a_i\cdot p_i^{-1}) \,\mathrm{mod}\,N\) има горње ограничење \(10^{15}\) (јер је \(N\) велики број), па би множење тог броја са бројем \(p_i\) чије је горње ограничење \(10^{10}\) вероватно довело до прекорачења. Чак и да се редослед операција замени и да се број \((a_i\cdot p_i)\,\mathrm{mod}\,N\) множи бројем \(p_i^{-1}\) који је доста мањи нас не би заштитило, јер би се множили бројеви чија су ограничења \(10^{15}\) и \(10^5\), чији се производ опет не може репрезентовати са 64 бита.

Безбедно решење се може добити ако се примети да је \(N = p_i\cdot n_i\) и да се заправо рачуна вредност израза \((a_i\cdot p_i^{-1}\cdot p_i) \,\mathrm{mod}\,(p_i\cdot n_i)\) који и у бројиоцу и у имениоцу има заједнички фактор \(p_i\). Вредност тог израза једнака је вредности израза \(p_i \cdot ((a_i\cdot p_i^{-1}) \,\mathrm{mod}\,n_i))\). Ова форма нам гарантује да неће доћи до прекорачења. Наиме, бројеви \(a_i\), \(p_i^{-1}\) и \(n_i\) су мањи од \(10^5\), па је такав и \((a_i\cdot p_i^{-1}) \,\mathrm{mod}\,n_i\). Пошто је \(p_i\) мањи од \(10^{10}\) њихов је производ мањи од \(10^{15}\) и може се представити 64-битним целим бројем.

Када постоји велика опасност од прекорачења, обично је најбезбедније решење (које додуше користи мало више операција него што је то стварно неопходно) је да се дефинишу посебне функције за сабирање и множење по модулу и да се оне позивају на месту сваког сабирања и множења у коду. Као што смо видели у овом примеру, чак ни то није гаранција и потребно је било веома пажљиво анализирати проблем да би се извела формула која гарантује да до прекорачења неће доћи.

#include <iostream>
#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;
}

// t je inverz broja a po modulu n tj. broj takav da je (a * t) mod n = 1
// funkcija vraca da li je uspela da izracuna broj t
bool inverz(long long a, long long n, long long& t) {
  long long r = n, r1 = a;
  t = 0; long long t1 = 1;
  while (r1 > 0) {
    long long q = r / r1;
    long long tmp;
    
    tmp = r;
    r = r1;
    r1 = tmp - q*r1;
    
    tmp = t;
    t = t1;
    t1 = tmp - q*t1;
  }
  if (t < 0) t += n;
  return r == 1;
}

// proizvod brojeva x i y po modulu n
long long pm(long long x, long long y, long long n) {
  return ((x % n) * (y % n)) % n;
}

// zbir brojeva x i y po modulu n
long long zm(long long x, long long y, long long n) {
  return ((x % n) + (y % n)) % n;
}

// racuna (z * x) mod (z * y)
long long pmp(long long x, long long y, long long z) {
  return z * (x % y);
}

// na osnovu kineske teoreme o ostacima se izracunava rezultat tako da
// za sve elemente nizova n i a vazi da je rezultat mod n[i] = a[i]
// funkcija vraca da li je rezultat bilo moguce naci
bool kto(long long n[], long long a[], int duzina, long long& rezultat) {
  long long N = 1;
  for (int i = 0; i < duzina; i++)
    N *= n[i];

  rezultat = 0;
  for (int i = 0; i < duzina; i++) {
    long long pi = N / n[i];
    long long pi_inv;
    if (!inverz(pi, n[i], pi_inv))
      return false;
    // rezultat = (rezultat + (a[i] * pi_inv * p_i) % N) % N
    // zbod prekoracenja moramo koristiti vezu
    // rezultat = (rezultat + ((p_i * (a[i] * pi_inv)) % (p_i * n[i])) % N
    rezultat = zm(rezultat, pmp(pm(a[i], pi_inv, N), n[i], pi), N);
  }
  return true;
}
 
int main(void) {
  // ucitavamo ulazne podatke
  long long a[3], n[3];
  for (int i = 0; i < 3; i++)
    cin >> a[i] >> n[i];

  // rezultat izracunavamo na osnovu kineske teoreme o ostacima
  long long rezultat;
  if (!kto(n, a, 3, rezultat))
    cout << "Nisu uzajamno prosti" << endl;

  // prijavljujemo rezultat
  cout << rezultat << endl;
  
  return 0;
}

Примена Безуове теореме на две једначине

Поред општег поступка за решавање проблема за \(k\) остатака, у случају само два остатка постоји и веома сличан, али мало другачије формулисан поступак, који се заснива на томе да умемо да решимо систем од две једначине (две конгруенције), применом Безуове теореме.

За узајамно просте бројеве \(n_1\) и \(n_2\), на основу Безуове теореме могу се пронаћи бројеви \(s\) и \(t\) такви да важи да је \(s\cdot n_1 + t\cdot n_2 = 1\). Може се лако показати да коефицијент \(s\) представља модуларни инверз броја \(n_1\) по модулу \(n_2\), док коефицијент \(t\) представља модуларни инверз броја \(n_2\) по модулу \(n_1\). Зато број \(r_{12} = a_1\cdot t \cdot n_2 + a_2 \cdot s\cdot n_1\) тј. његов остатак по модулу \(n_1\cdot n_2\), евентуално увећан за \(n_1 \cdot n_2\) ако је негативан, при дељењу са \(n_1\) даје остатак \(a_1\), а при дељењу са \(n_2\) даје остатак \(a_2\).

Дакле, ако Кинеску теорему примењујемо на два броја, не морамо два пута независно рачунати модуларни инверз, него оба потребна коефицијента можемо добити једном применом проширеног Еуклидовог алгоритма.

Ако има више бројева на које је потребно применити Кинеску теорему, након одређивања решења за прва два, исти поступак се примењује да се одреди броји који при дељењу са \(n_1\cdot n_2\) даје остатак \(r_{12}\), а при дељењу са \(n_3\) даје остатак \(a_3\). Ако је \(k > 3\), поступак се наставља на исти начин, док се не добије коначан резултат.

Приметимо да се у формули \((a_1\cdot t \cdot n_2 + a_2 \cdot s\cdot n_1) \,\mathrm{mod}\,(n_1\cdot n_2)\) множе два пута по три броја, као и да је модул \(n_1\cdot n_2\) прилично велики број, па привремени резултати могу да прекораче опсег 64-битног типа, чак иако су сви \(a_i\) и \(n_i\) 32-битни целих бројеви и ако се модули рачунају пре и након сваке операције множења. То се може предупредити ако се примети да је \((a_1\cdot t\cdot n_2) \,\mathrm{mod}\,(n_1\cdot n_2) = n_2 \cdot ((a_1 \cdot t) \,\mathrm{mod}\,n_1)\) и да је \((a_2\cdot s\cdot n_1)\,\mathrm{mod}\,(n_1\cdot n_2) = n_1\cdot ((a_2\cdot s) \,\mathrm{mod}\,n_2)\).

#include <iostream>

using namespace std;

// proizvod brojeva x i y po modulu n
long long pm(long long x, long long y, long long n) {
  return ((x % n) * (y % n)) % n;
}

// racuna (z * x) mod (z * y)
long long pmp(long long x, long long y, long long z) {
  return z * (x % y);
}

// zbir brojeva x i y po modulu n
long long zm(long long x, long long y, long long n) {
  return ((x % n) + (y % n)) % n;
}

// izracunavanje Bezuovih koeficijenata prosirenim Euklidovim
// algoritom - nakon primene funkcije vazi:
//    s*a + t*b = nzd(a, b)
//    pri cemu funkcija vraca vrednost nzd(a, b)
long long bezu(long long a, long long b, long long& s, long long& t) {
  long long r0 = a, r1 = b;
  long long s0 = 1, s1 = 0;
  long long t0 = 0, t1 = 1;
  while (r1 > 0) {
    long long q = r0 / r1;
    long long tmp;
    
    tmp = r0;
    r0 = r1;
    r1 = tmp - q*r1;
    
    tmp = s0;
    s0 = s1;
    s1 = tmp - q*s1;
    
    tmp = t0;
    t0 = t1;
    t1 = tmp - q*t1;
  }
  s = s0; t = t0;
  return r0;
}

// kineska teorema o ostacima za dva broja
long long kto(long long a1, long long n1, long long a2, long long n2) {
  long long m1, m2;
  // izracunavamo bezuove koeficijente tako da je m1*n1 + m2*n2 = 1
  bezu(n1, n2, m1, m2);
  // resenje je (a1*m2*n2 + a2*m1*n1) % (n1*n2),
  // ali zbog prekoracenja moramo transformisati formulu
  long long n = n1*n2;
  long long x = zm(pmp(pm(a1, m2, n), n1, n2),
                   pmp(pm(a2, m1, n), n2, n1), n);
  // popravak ako je resenje eventualno negativno
  if (x < 0)
    x += n;
  return x;
}

int main() {
  // ucitavamo prvi par
  long long a, n;
  cin >> a >> n;
  for (int j = 1; j < 3; j++) {
    // ucitavamo naredni par
    long long aj, nj;
    cin >> aj >> nj;
    // Kineskom teoremom izracunavamo resenje za tekuce vrednosti a, n i
    // ucitane vrednosti aj, nj i pripremamo a i n za sledecu iteraciju
    a = kto(a, n, aj, nj);
    n *= nj;
  }

  // ispisujemo resenje
  cout << a << endl;
  
  return 0;
}