Question

Buna!
Ma poate ajuta cineva la problema:
#2795 Resturi1
Cerința
Subprogramul resturi are patru parametri, n, x, y și r, prin care primește câte un număr natural din intervalul [1,109], r
Scrieţi definiţia completă a subprogramului.

Restricții și precizări
1 ≤ r ordinea parametrilor este n x y r

Exemplu
Pentru n=200, x=5, y=14 și r=2, subprogramul returnează numărul 3 (pentru numerele 2, 72 și 142 atât restul împărțirii la 5, cât și restul împărțirii la 14, este 2).

Important
Soluția propusă va conține definiția subprogramului cerut. Prezența în soluție a altor instrucțiuni poate duce erori de compilare sau de execuție care vor avea ca efect depunctarea soluției.

Eu am scris urmatorul cod, care functioneaza, dar la teste iau limita de timp depasita si doar 80 pct:

int resturi (unsigned int n, unsigned int x, unsigned int y, unsigned int r)
{
int ctr=0;
for (int i=1; i<=n;i++)
{

if (i%x==r && i%y==r)
ctr++;
}
return ctr;
}

Multumesc!

Answer 1

Răspuns:

Programul tau este O(n).

Solutia optima e O(log n)

Explicație:

Un numar m, daca da acelasi rest prin impartirea la 2 numere diferite, putem spune despre el ca:

$m = k_1\cdot x + r = k_2\cdot y + r, k_1, k_2\in \mathbb{Z}\\ \\ m = k_1\cdot x + r = k_2\cdot y + r\Bigg|-r \\ \\ m - r = k_1 \cdot x = k_2 \cdot y \implies m-r \in M_{[x,y]} \iff m = k\cdot [x,y] + r$

Mai intai trebuie sa calculam [x,y](il voi nota cu z)

Apoi, trebuie sa aflam cate numere de forma $k\cdot z + r$ sunt in multimea {1,2,..., n}

Rezultatul este:

$\begin{cases}n / z, \:daca\: n\:\% \:z < r\\ n / z + 1, altfel\end{cases}$

O implementare a acestui algoritm:

int resturi(unsigned int n, unsigned int x, unsigned int y, unsigned int r){

   unsigned long long int z = 1ULL * x * y;//Daca x si y sunt prea mari avem overflow pentru tipul int

   while(x!=0){

    unsigned int rr = y % x;

       y = x;

       x = rr;

   }

   z /= y;

   // aici z are valoarea cmmmc-ului dintre x si y

   if(n%z < r)return n / z;

   else return n / z + 1;

}