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:
[tex]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[/tex]
Mai intai trebuie sa calculam [x,y](il voi nota cu z)
Apoi, trebuie sa aflam cate numere de forma [tex]k\cdot z + r[/tex] sunt in multimea {1,2,..., n}
Rezultatul este:
[tex]\begin{cases}n / z, \:daca\: n\:\% \:z < r\\ n / z + 1, altfel\end{cases}[/tex]
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;
}
