2960 - Abx

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

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

Cerința

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

Dacă există două puteri egal depărtate de  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 input.txt 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  (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 output.txt va conține N linii, pe fiecare linie i (1 ≤ i ≤ N) 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>