★Math & Geometry Advanced I - 1 Solved★

★ 1011 Fly me to the Alpha Centauri ★

import sys
input=sys.stdin.readline

for _ in range(int(input())):
    x,y=map(int,input().split())
    diff=y-x
    closest_root=int(diff**(1/2))
    if diff == (closest_root**2):
        print(closest_root*2-1)
    elif (diff-(closest_root**2))<=closest_root:
        print(closest_root*2)
    else:
        print(closest_root*2+1)

 

🍋 kn은 kn-1 / kn / kn+1 중 한 개만 가능 + 맨 앞과 맨 뒤의 거리 step은 1만 가능하다는 조건 하에 수학 규칙성을 찾는 문제

→ y-x를 diff라고 한다면, 중복된 step 간격 없이 오름차순 - 내림차순 형태의 수열을 형성할 수 있는 diff는 제곱수만 가능하다.

🍋 위 그림과 같이 (입력 받은 두 x와 y의 diff를 n이라 가정)

① n이 제곱수라면 1 + 2 + ... + (√n-1) + √ n + ( √ n-1) + ... + 2 + 1은 ( √ n)^2이다. 이 때의 step은 2*( √ n) - 1.

 

② floor(√n)과 floor( √(n))+1 사이의 숫자

→ floor( √n)+1 ≤ n ≤ floor( √ n)+ √n이라면 step은 2*( floor(√ n))

→ floor( √n) + √n < n < floor( √(n))+1이라면 step은 2*(floor( √n))+1

 

🍋 floor(√n)만큼 오른쪽 감소부분 숫자가 1씩 감소하는 부분 수열이 될 때까지 1씩 부분부분 숫자가 증가하고, floor( √n)만큼 왼쪽 증가부분 숫자가 1씩 증가하는 부분 수열이 될 때까지 1씩 부분부분 숫자가 증가한다.

---