# PBinfo #2960 – abx – Rezolvare C++

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

## Enunț

Un număr natural n se numește putere dacă există două numere naturale a, b, a ≥ 1, b ≥ 2 astfel încât \(n = a^b\). De exemplu, numerele 32 , 169 , 1 sunt puteri (\(32 = 2^5\) , \(169 = 13^2\) , \(1 = 1^2\)), iar 72 , 2000 și 31 nu sunt puteri.
Se citesc numerele naturale N , M și un șir de N numere naturale \(x_1, x_2, …, x_N\) din intervalul [1,M].

Cerința
Pentru fiecare din cele N numere \(x_i\) determinați câte un număr natural \(r_i\) din intervalul [1,M], cu proprietatea că \(r_i\) este o putere și pentru orice altă putere p din intervalul [1,M] este îndeplinită condiția \(|x_i – r_i| ≤ |x_i – p|\), unde |x| reprezintă valoarea absolută a lui x (modulul).
Dacă există două puteri egal depărtate de \(x_i\) se va alege puterea cea mai mică. De exemplu pentru numărul 26, dintre puterile 25 și 27 va fi ales numărul 25.

Date de intrare
Fișierul de intrare abx.in conține pe prima linie două numere N și M, iar pe fiecare dintre următoarele N linii se găsește câte un număr natural \(x_i\) (1 ≤ i ≤ N), cu semnificația de mai sus. Numerele aflate pe aceeași linie a fișierului sunt separate prin câte un spațiu.

Date de ieșire
Fișierul de ieșire abx.out va conține N linii, pe fiecare linie i (1 ≤ i ≤ N) aflându-se numărul natural \(r_i\) cu semnificația din enunț.

Restricții și precizări

\(1 ≤ N ≤ 5000\)
\(10 ≤ M ≤ 10^{18}\)
Pentru teste valorând 40 de puncte \(M ≤ 5000\)
Pentru teste valorând 70 de puncte \(M ≤ 10^9\)
În concurs s-au acordat 10 puncte din oficiu. Aici se acordă pentru testul din exemplu.

Exemplu:
abx.in

8 1000
345
99
999
500
123
124
99
256
abx.out

343
100
1000
512
121
125
100
256
Explicație
\(343 = 7^3\)
\(100 = 10^2\)
\(1000 = 10^3\)
\(512 = 2^9\)
\(121 = 11^2\)
\(125 = 5^3\)
\(100 = 10^2\)
\(256 = 2^8\)

## Cod sursă C++

```cpp
#include <bits/stdc++.h>
using namespace std;
int n;
long long m, a;
inline long long lgput(int x, int y){
    long long ans = 1, aux = x;
    for(int p = 1; p <= y ; p = p << 1){
        if(y & p) ans = ans * aux;
        aux = aux * aux;
    }
    return ans;
}
inline int cautb(long long x, int put){
    long long st = 1, dr = pow(x, 1.0 / put);
    while(st <= dr){
        int mij = (1LL * st + dr) / 2;
        if(lgput(mij, put) > x) dr = mij - 1;
        else st = mij + 1;
    }
    return dr;
}
int main()
{
    ifstream f("abx.in");
    ofstream g("abx.out");
    f >> n >> m;
    for(int i=1; i <= n; ++i){
        f >> a;
        long long sol = 0, dif = m + 100;
        for(int j=2; j <= 60 ; ++j){
            long long y = cautb(a, j);
            long long z = lgput(y, j);
            if(abs(a - z) <= dif && z <= m)
                sol = z, dif = abs(a - z);
            z = lgput(y + 1, j);
            if(abs(a - z) < dif && z <= m)
                sol = z, dif = abs(a - z);
        }
        g << sol << "\n";
    }
    return 0;
}
```

## Resurse

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