Kaosar і мінімізація#12437

Kaosar і мінімізація (Розбір)

Автор задачі:	Al_Kaosar
Підготовлено:	MathModel
Відредаговано:	MathModel

Розв'язок

Мета полягає в мінімізації $f (x, y) = ∣ n - x^{y} ∣ + ∣ x - y ∣$ f(x, y) = |n - x^y| + |x - y| для $x, y \geq 1$ x, y \ge 1.

Для фіксованого $y$ значення $x$ , при якому $x^{y}$ x^y є найближчим до $n$ , дорівнює або $⌊ n^{1/ y} ⌋$ \lfloor n^{1/y} \rfloor, або $⌈ n^{1/ y} ⌉$ \lceil n^{1/y} \rceil. Оскільки $n \leq 1 0^{18}$ n \le 10^{18}, якщо $x \geq 2$ x \ge 2, то $y$ може бути не більшим за приблизно $60$ , бо $2^{60} > 1 0^{18}$ 2^{60} > 10^{18}. Якщо $x = 1$ x=1, вираз набуває вигляду $∣ n - 1∣ + ∣1 - y ∣$ |n-1| + |1-y|, і його мінімум досягається при $y = 1$ y=1, даючи значення $n - 1$ n-1.

Можна перебрати всі можливі значення $y$ від $1$ до $62$ . Для кожного $y$ ми оцінюємо $x \approx n^{1/ y}$ x \approx n^{1/y}. Через можливі проблеми з точністю чисел з плаваючою комою для $n = 1 0^{18}$ n=10^{18} безпечніше знаходити $x$ за допомогою pow(n, 1/y) і потім перевіряти невеликий діапазон навколо нього, або використовувати бінарний пошук, щоб знайти $x$ таке, що $x^{y} \leq n$ x^y \le n.

Для кожного $y \in [1, 62]$ y \in [1, 62] ми перевіряємо $x_{c an d} \in {⌊ n^{1/ y} ⌋, ⌈ n^{1/ y} ⌉}$ x_{cand} \in \{\lfloor n^{1/y} \rfloor, \lceil n^{1/y} \rceil\}. Також перевіряємо кандидат $x = y$ x=y, оскільки тоді друга частина виразу дорівнює нулю.

Загальна складність становить $O (lo g n)$ O(\log n).

def solve():
 n=int(input())
 ans=n-1
 K=n.bit_length()
 for y in range(2,K+1):
  r=int(n**(1/y))
  for x in(r,r+1):
   if x>0:
    p=pow(x,y)
    ans=min(ans,abs(n-p)+abs(x-y))
 print(ans)

for _ in range(int(input())):
 solve()

Python