Kaosar and Minimization#12437

Kaosar and Minimization (Editorial)

Problem Author:	Al_Kaosar
Prepared by:	MathModel
Edited by:	MathModel

Solution

The objective is to minimize $f (x, y) = ∣ n - x^{y} ∣ + ∣ x - y ∣$ f(x, y) = |n - x^y| + |x - y| for $x, y \geq 1$ x, y \ge 1.

For a fixed $y$ , the value of $x$ that makes $x^{y}$ x^y closest to $n$ is either $⌊ n^{1/ y} ⌋$ \lfloor n^{1/y} \rfloor or $⌈ n^{1/ y} ⌉$ \lceil n^{1/y} \rceil. Since $n \leq 1 0^{18}$ n \le 10^{18}, if $x \geq 2$ x \ge 2, then $y$ can be at most $\approx 60$ because $2^{60} > 1 0^{18}$ 2^{60} > 10^{18}. If $x = 1$ x=1, the expression becomes $∣ n - 1∣ + ∣1 - y ∣$ |n-1| + |1-y|, which is minimized at $y = 1$ y=1, yielding $n - 1$ n-1.

We can iterate through all possible values of $y$ from $1$ to $62$ . For each $y$ , we estimate $x \approx n^{1/ y}$ x \approx n^{1/y}. Due to potential floating-point precision issues with $n = 1 0^{18}$ n=10^{18}, it is safer to find $x$ using pow(n, 1/y) and then check a small range around it, or use binary search to find $x$ such that $x^{y} \leq n$ x^y \le n.

For each $y \in [1, 62]$ y \in [1, 62], we test $x_{c an d} \in {⌊ n^{1/ y} ⌋, ⌈ n^{1/ y} ⌉}$ x_{cand} \in \{\lfloor n^{1/y} \rfloor, \lceil n^{1/y} \rceil\}. We also check $x = y$ x=y as a candidate, as it nullifies the second term of the expression.

The total complexity is $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