Editing 2960 - Abx

Un număr natural <code>n</code> se numește putere dacă există două numere naturale <code>a</code>, <code>b</code>, <code>a ≥ 1</code>, <code>b ≥ 2</code> astfel încât . De exemplu, numerele <code>32</code> , <code>169</code> , <code>1</code> sunt puteri ( ,  ,  ), iar <code>72</code> , <code>2000</code> și <code>31</code> nu sunt puteri.

Se citesc numerele naturale <code>N</code> , <code>M</code> și un șir de <code>N</code> numere naturale  din intervalul <code>[1,M]</code>.

= Cerința =
Pentru fiecare din cele <code>N</code> numere  determinați câte un număr natural  din intervalul <code>[1,M]</code>, cu proprietatea că  este o putere și pentru orice altă putere <code>p</code> din intervalul <code>[1,M]</code> este îndeplinită condiția , unde <code>|x|</code> reprezintă valoarea absolută a lui <code>x</code> (modulul).

Dacă există două puteri egal depărtate de  se va alege puterea cea mai mică. De exemplu pentru numărul <code>26</code>, dintre puterile <code>25</code> și <code>27</code> va fi ales numărul <code>25</code>.

= Date de intrare =
Fișierul de intrare <code>input.txt</code> conține pe prima linie două numere <code>N</code> și <code>M</code>, iar pe fiecare dintre următoarele <code>N</code> linii se găsește câte un număr natural  (<code>1 ≤ i ≤ N</code>), 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 <code>output.txt</code> va conține <code>N</code> linii, pe fiecare linie <code>i</code> (<code>1 ≤ i ≤ N</code>) aflându-se numărul natural  cu semnificația din enunț.

= Restricții și precizări =

* 1<=n<=5000
* 10<=m<=10^18

== Exemplul 1 ==
input.txt:

8 1000

345

99

999

500

123

124

99

256

output.txt:

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

== Exemplul 2 ==
input.txt:

999999999999 1000

345

99

999

500

123

124

99

256

Output:

Error: n is not within the valid range (1 <= n <= 5000)

== Rezolvare ==
<syntaxhighlight lang="python3" line="1">
import math
import sys

def verify_constraints(n, m):
    if not (1 <= n <= 5000):
        sys.exit("Error: n is not within the valid range (1 <= n <= 5000)")

    if not (10 <= m <= 10**18):
        sys.exit("Error: m is not within the valid range (1 <= m <= 10^18)")

def lgput(x, y):
    ans = 1
    aux = x
    p = 1
    while p <= y:
        if y & p:
            ans *= aux
        aux *= aux
        p <<= 1
    return ans

def cautb(x, put):
    st = 1
    dr = int(x ** (1 / put))
    while st <= dr:
        mij = (st + dr) // 2
        if lgput(mij, put) > x:
            dr = mij - 1
        else:
            st = mij + 1
    return dr

with open("input.txt", "r") as f, open("output.txt", "w") as g:
    n, m = map(int, f.readline().split())
    verify_constraints(n, m)
    a_values = [int(f.readline()) for _ in range(n)]

    for a in a_values:
        sol = 0
        dif = m + 100
        
        for j in range(2, 61):
            y = cautb(a, j)
            z = lgput(y, j)
            
            if abs(a - z) <= dif and z <= m:
                sol = z
                dif = abs(a - z)
            
            z = lgput(y + 1, j)
            
            if abs(a - z) < dif and z <= m:
                sol = z
                dif = abs(a - z)
        
        g.write(str(sol) + "\n")

</syntaxhighlight>