Kaosar və Minimallaşdırma#12437

Kaosar və Minimallaşdırma (Həll təhlili)

Məsələnin müəllifi:	Al_Kaosar
Hazırlayan:	MathModel
Redaktə edən:	MathModel

Həll

Məqsəd $x, y \geq 1$ x, y \ge 1 üçün $f (x, y) = ∣ n - x^{y} ∣ + ∣ x - y ∣$ f(x, y) = |n - x^y| + |x - y| ifadəsini minimum etməkdir.

Sabit $y$ üçün $x^{y}$ x^y qiymətini $n$ -ə ən yaxın edən $x$ ya $⌊ n^{1/ y} ⌋$ \lfloor n^{1/y} \rfloor, ya da $⌈ n^{1/ y} ⌉$ \lceil n^{1/y} \rceil olur. $n \leq 1 0^{18}$ n \le 10^{18} olduğuna görə, əgər $x \geq 2$ x \ge 2-dirsə, onda $y$ ən çox təxminən $60$ ola bilər, çünki $2^{60} > 1 0^{18}$ 2^{60} > 10^{18}. Əgər $x = 1$ x=1 olarsa, ifadə $∣ n - 1∣ + ∣1 - y ∣$ |n-1| + |1-y| şəklini alır və bu da $y = 1$ y=1 olduqda minimum olur, nəticə isə $n - 1$ n-1 edir.

Biz $y$ -nin bütün mümkün qiymətlərini $1$ -dən $62$ -yə qədər yoxlaya bilərik. Hər bir $y$ üçün $x \approx n^{1/ y}$ x \approx n^{1/y} qiymətini təxmin edirik. $n = 1 0^{18}$ n=10^{18} üçün üzən nöqtəli hesablamalarda dəqiqlik problemləri yarana biləcəyindən, $x$ -i pow(n, 1/y) ilə tapıb onun ətrafında kiçik bir aralığı yoxlamaq, yaxud $x^{y} \leq n$ x^y \le n şərtini ödəyən $x$ -i tapmaq üçün ikili axtarışdan istifadə etmək daha təhlükəsizdir.

Hər bir $y \in [1, 62]$ y \in [1, 62] üçün $x_{c an d} \in {⌊ n^{1/ y} ⌋, ⌈ n^{1/ y} ⌉}$ x_{cand} \in \{\lfloor n^{1/y} \rfloor, \lceil n^{1/y} \rceil\} namizədlərini yoxlayırıq. Həmçinin $x = y$ x=y namizədini də yoxlayırıq, çünki bu halda ifadənin ikinci hissəsi sıfır olur.

Ümumi mürəkkəblik $O (lo g n)$ O(\log n)-dir.

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