Haidora və çubuqlar (Həll təhlili)

Həll

Üçbucaq Quruluşu ilə qurmaq optimaldır, yəni $1$-dən $m$-ə qədər ədədləri toplamağa davam edirik ki, cəmi S \le x olsun. Biz bilirik ki, ilk $m$ tam ədədin cəmi:

Qeyd edin ki, $T(m)$ artır! , buna görə də T(m) \le m olan maksimum $m$ üçün ikili axtarış edə bilərik, sərhədlər l=1 və r=2 \cdot 10^9 olacaq ki, bu da təhlükəsizdir, çünki T(2 \cdot 10^9) > 2 \cdot 10^{18}-dir ki, bu da problemi həll etmək üçün kifayətdir və həmçinin C++ üçün uzun 'long long' aralığına uyğundur.

$m$-ni əldə etdikdən sonra maksimum çubuq uzunluğunu tapmağa gəlirik, bu halda cavab $m$-nin maksimumu olacaq — üçbucaq quruluşunda istifadə etdiyimiz ən böyük tam ədəd və qalan tam ədədlərin maksimumu, rəsmi olaraq

Komplekslik \mathcal{O}(\log(2\cdot 10^9) \cdot t).

def T(n):return (n*(n+1))//2

def solve():
    n=int(input())
    l,r=1,2*10**9
    while(l<=r):
        m=(l+r)//2
        if(T(m)<n<T(m+1)):
            ans=m+1
            break
        if(T(m)==n):
            ans=m
            break
        if(T(m)<n):
            l=m+1
        if(T(m)>n):
            r=m-1
    if(T(ans)>n):ans-=1
    print(ans,max(ans,n-T(ans-1)))

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