# PBinfo #3401 – spp – Rezolvare C++

Sursa: Codul lui Andrei
Limbaj: C++
Autor rezolvare: deivid

## Enunț

După o zi plină, trei băieți se joacă cu numere. În fiecare seară, unul dintre ei alege un număr x, iar altul un număr y mai mare sau egal cu x. Al treilea propune ceva mai interesant. Astfel, el alege să le spună aproape instantaneu suma pătratelor perfecte de la x și y. Voi trebuie să rezolvați ceva asemănător, doar că știți numai ce zice primul și ultimul băiat. Pentru a-i verifica dacă greșesc la calcule, în schimb, trebuie să găsiți numărul pe care l-ar putea spune al doilea.

Formal, pentru două numere x și y se definește SPP(x,y) = x2 + (x+1)2 +...+ y2 (suma pătratelor perfecte de la x la y).

Se dau Q întrebări de tipul x p și se cere cel mai mic y mai mare sau egal ca x pentru care SPP(x,y) ≥ p2.

Cerința
Să se calculeze pentru fiecare întrebare p minimum, pentru care relația este satisfăcută.

Date de intrare
Fișierul de intrare spp.in conține pe prima linie un număr natural Q. Pe liniile 2, 3, …, Q+1 se află câte o pereche x p care satisface restricțiile.

Date de ieșire
Fișierul de ieșire spp.out va conține răspunsul la fiecare întrebare.

Restricții și precizări

Q ≤ 100.000
1 ≤ x ≤ 100.000
1 ≤ p ≤ 1.000.000.000
Pentru 30% din teste, Q ≤ 100 sau p ≤ 1000

Exemplu:
spp.in

2
1 5
10 19
spp.out

4
12
Explicație
12 + 22 + 32 + 42 = 30 ≥ 52.
102 + 112 + 122 = 365 ≥ 192.

## Cod sursă C++

```cpp
#include <fstream>
#include <iostream>
using namespace std;
ifstream f("spp.in");
ofstream g("spp.out");
int q, x, p;
int binarys(int x, int st, int dr, long long pp)
{
   int sol  = 0;
   long long px = (1LL * x * (x + 1) * (2 * x + 1)) / 6;
   while (st <= dr) {
       int mid = (st + dr) >> 1;
       long long py = (1LL * mid * (mid + 1) * (2 * mid + 1)) / 6;
       if (py - px >= pp)
           sol = mid, dr = mid - 1;
       else
           st = mid + 1;
   }
   return sol;
}
int main()
{
   int i;
   f >> q;
   for (i = 1; i <= q; i++) {
       f >> x >> p;
       int y = binarys(x - 1, x, x + 1500000, 1LL * p * p);
       g << y << '\n';
   }
   return 0;
}
```

## Resurse

- [Pagina originală](https://codulluiandrei.ro/rezolvari/pbinfo/3401)
- [Sursa C++](https://codulluiandrei.ro/rezolvari/pbinfo/3401/cod.cpp)
- [Sursa pe GitHub](https://raw.githubusercontent.com/codulluiandrei/pbinfo/main/pbinfo-3401/main.cpp)
- [Cursuri de informatică pentru BAC](https://codulluiandrei.ro/academia/info-curs/pachet-cpp/)