Problem:


Score : 700 points

Problem Statement

10^{10^{10}} participants, including Takahashi, competed in two programming contests.
In each contest, all participants had distinct ranks from first through 10^{10^{10}}-th.

The score of a participant is the product of his/her ranks in the two contests.

Process the following Q queries:

In the i-th query, you are given two positive integers A_i and B_i. Assuming that Takahashi was ranked A_i-th in the first contest and B_i-th in the second contest, find the maximum possible number of participants whose scores are smaller than Takahashi's.

Constraints

1 \leq Q \leq 100

1\leq A_i,B_i\leq 10^9(1\leq i\leq Q)

All values in input are integers.

Input

Input is given from Standard Input in the following format:

Q
A_1 B_1
:
A_Q B_Q

Output

For each query, print the maximum possible number of participants whose scores are smaller than Takahashi's.

Sample Input 1

8
1 4
10 5
3 3
4 11
8 9
22 40
8 36
314159265 358979323

Sample Output 1

1
12
4
11
14
57
31
671644785

Let us denote a participant who was ranked x-th in the first contest and y-th in the second contest as (x,y).

In the first query, (2,1) is a possible candidate of a participant whose score is smaller than Takahashi's. There are never two or more participants whose scores are smaller than Takahashi's, so we should print 1.



Sample input:
8
1 4
10 5
3 3
4 11
8 9
22 40
8 36
314159265 358979323


Sample output:
1
12
4
11
14
57
31
671644785

Submission status: Time Limit Exceeded

Solution code:
num = int(input())
rankList = []

for x in range(0,num):
	inp = list(map(int, input().split()))
	rankList.append(inp)


for rank in rankList:
	count = 0
	score = rank[0] * rank[1]
	usedRnak1 = [rank[0]]
	usedRnak2 = [rank[1]]

	for r1 in range(1,rank[0]):
		if (r1 in usedRnak1) is False:
			if score % r1 == 0:
				r2 = int(score / r1) - 1
			else:
				r2 = int(score / r1)

			flg = True
			while r2 in usedRnak2:
				r2 = r2 -1
				if r2 == 0:
					flg = False
					break
			if flg:
				# print(str(r1)+":"+str(r2))
				count += 1
				usedRnak1.append(r1)
				usedRnak2.append(r2)

	for r2 in range(1,rank[1]):
		if (r2 in usedRnak2) is False:
			if score % r2 == 0:
				r1 = int(score / r2) - 1
			else:
				r1 = int(score / r2)

			flg = True
			while r1 in usedRnak1:
				r1 = r1 -1
				if r1 == 0:
					flg = False
					break
			if flg:
				# print(str(r1)+":"+str(r2))
				count += 1
				usedRnak1.append(r1)
				usedRnak2.append(r2)

	print(count)

Submission status: Time Limit Exceeded

Solution code:
# PROBLEM D
Q = int(input())
for _ in range(Q):
    a, b = sorted([int(s) for s in input().split()])
    c = 1
    sol = 0
    while True:
        d = (a * b) // c
        while c * d >= a * b:
            d -= 1
        if c > d:
            break
        if c < d:
            sol_ = (c != a) + (d != b)
        else:
            sol_ = (c != a) and (c != b)
        #print('candidate', c, d, sol_)
        sol += sol_
        c += 1
    print(sol)

Submission status: Time Limit Exceeded

Solution code:
q = int(input())
countq = 0
while countq < q:
    countq += 1
    s = input().split()
    a = int(s[0])
    b = int(s[1])
    tempb = [b]
    for ai in range(1,a*b+1):
        if ai == a:
            continue
        bi = int(a*b/ai)
        if bi < 1:
            break
        while (bi in tempb) or (ai * bi >= a*b ):
            bi -= 1
        if bi < 1:
            break
        tempb.append(bi)
    print(len(tempb)-1)

Submission status: Time Limit Exceeded

Solution code:
q = int(input())
countq = 0
while countq < q:
    countq += 1 
    s=input().split()
    a = int(s[0])
    b = int(s[1])
    tempa = [a]
    tempb = [b]
    for ai in range(1,a*b+1):
        if ai in tempa:
            continue
        bi = int(a*b/ai)
        while (bi in tempb) or (ai * bi >= a*b ):
            bi -= 1
        if bi < 1:
            break
        tempb.append(bi)
        tempa.append(ai) 
    print(len(tempa)-1)

Submission status: Time Limit Exceeded

Solution code:
Q = int(input())
A, B = [[], []]
for x in range(Q):
 A, B = (int(x) for x in input().split())
 lst = [[x for x in range(A*B) if x not in (0, A)], [x for x in range(A*B) if x not in (0, B)][::-1]]
 count = 0
 flag = 1
 while lst[0] and lst[1]:
  a = lst[0].pop(0)
  if a*lst[1][::-1][0] >= A*B:
   break
  while lst[1]:
#   print(*lst)
   b = lst[1].pop(0)
   if a*b < A*B:
    count += 1
    break
 print(count)

Submission status: Time Limit Exceeded

Solution code:
Q=int(input())
for i in range(Q):
    x,y=list(map(int,input().split()))
    c=x*y-1
    z={}
    z[0]=y
    rest=0
    for i in range(1,x):
        j=c//i
        if j not in z.values():
            z[i]=j
    for i in range(x+1,c+1):
        j=c//i
        if j not in z.values():
            z[i]=j
        else:
            rest=j-1
            break


    print(len(z)-1+rest)

Submission status: Time Limit Exceeded

Solution code:
def exec():
    q = int(input())
    for _ in range(q):
        a,b = map(int, input().split())
        if a == 1:
            x1 = 2
        else:
            x1 = 1
        x2 = int((a*b) / x1)
        if x2 == b:
            x2 -= 1
        t = 0
        prevX2 = a*b
        while x1 < a*b:
            x2 = int(a*b / x1)
            x2 = min(x2, prevX2-1)
            if x2 == b:
                x2 -= 1
            while x2 > 0:
                #print(str(x1) + " " + str(x2))
                if x1 * x2 < a * b:
                    t += 1
                    prevX2 = x2
                    break;
                x2 -= 1
                if x2 == b:
                    x2 -= 1
            x1 += 1
            if x1 == a:
                x1 += 1
        print(t)

if __name__ == "__main__":
    exec()

Submission status: Time Limit Exceeded

Solution code:
q = int(input())
for i in range(q):
    ret = 0
    a = list(map(int,input().split()))
    a.sort(reverse=True)
    point = a[0]*a[1]
    leftCap = point
    rightCap = 1
    for j in reversed(range(1,point)):
        if(rightCap == a[1]):
            rightCap += 1
            continue
        if j * rightCap < point:
            rightCap += 1
            ret += 1
    print(ret)

Submission status: Time Limit Exceeded

Solution code:
import sys

Q=int(input())
l=[]
for i in range(Q):
	l.append(list(map(int,input().split())))

for item in l:
	count=0
	a=[]
	b=[]
	a.append(item[0])
	b.append(item[1])
	score=item[0]*item[1]
	i=score-1
	hoge=1
	while i>0:
		j=1
		while i*j<score:

			if(i not in a) and (j not in b):
				count+=1
				a.append(i)
				b.append(j)
				if i not in b and j not in a:
					count+=1
					a.append(j)
					b.append(i)
				#print(i)
				#print(j)
				#print("-----")
			j+=1
		i-=1
	print(count)

Submission status: Time Limit Exceeded

Solution code:
def pair(x, y):
    count = 0
    a = x * y
    temp = a
    for i in range(1, a):
        if temp != int((a - 1) / i):
            if i == x or int((a - 1) / i) == y:
                continue
            # print(i, int((a - 1) / i))
            count += 1
            temp = int((a - 1) / i)
    return count

q = int(input())

for i in range(q):
    a , b = map(int, input().split(' '))
    print(pair(a,b))

Submission status: Time Limit Exceeded

Solution code:
q = int(input())

for i in range(q):
    count = 0
    a, b = map(int, input().split())
    s = set()
    s.add(b)

    score = a * b
    try:
        for j in range(1, score):
            if j != a:
                num = score // j
                while num >= 1:
                    if num * j < score and num not in s:
                        s.add(num)
                        count += 1
                        break
                    else:
                        num -= 1
                if num == 1:
                    raise Exception
                if num == 2 and b == 1:
                    raise Exception
    except:
        pass

    print(count)

Submission status: Time Limit Exceeded

Solution code:
q = int(input())

for i in range(q):
    count = 0
    a, b = map(int, input().split())
    s = set()
    s.add(b)

    score = a * b
    try:
        for j in range(1, score):
            if j != a:
                num = score // j
                while num >= 1:
                    if num * j < score and num not in s:
                        s.add(num)
                        count += 1
                        break
                    else:
                        num -= 1
                if num == 1:
                    raise Exception
    except:
        pass       

    print(count)

Submission status: Time Limit Exceeded

Solution code:
q = int(input())
a = []
b = []
for i in range(q):
  c = [int(i) for i in input().split()]
  a += [c[0]]
  b += [c[1]]

for i in range(q):
  prod = a[i] * b[i]
  cnt = 0
  used = prod
  for j in range(1, prod):
    if j == a[i]:
      continue
    
    upper_limit = prod // j
    for k in range(min(used - 1, upper_limit), 0, -1):
      if k == b[i] or j * k >= prod:
        continue
      else:
        used = k
        cnt += 1
        break
  print(cnt)

Submission status: Time Limit Exceeded

Solution code:
q = int(input())

for i in range(q):
    count = 0
    a, b = map(int, input().split())
    s = set()
    s.add(b)

    score = a * b
    for j in range(1, score):
        if j != a:
            num = score // j
            while num >= 1:
                if num * j < score and num not in s:
                    s.add(num)
                    count += 1
                    break
                else:
                    num -= 1
            if num == 1:
                break
    print(count)

Submission status: Time Limit Exceeded

Solution code:
q = int(input())
for i in range(q):
    ablist = sorted([int(x) for x in input().split()])
    rank = ablist[0]*ablist[1]
    j = 0
    dellist = []
    while(True):
        j += 1
        if j != ablist[0]:
            num = int(rank / j)
            if num*j == rank:
                num -= 1
            if num <= 0:
                break
            while((num in dellist) == True):
                num -= 1
                if num == 0:
                    break
            if num != 0:
                dellist.append(num)
            else:
                break
    print(len(dellist))

Submission status: Time Limit Exceeded

Solution code:
def exec():
    q = int(input())
    for _ in range(q):
        a,b = map(int, input().split())
        if a == 1:
            x1 = 2
        else:
            x1 = 1
        x2 = int((a*b) / x1)
        if x2 == b:
            x2 -= 1
        t = 0
        while x1 < a*b:
            while x2 > 0:
                if x1 * x2 < a * b:
                    t += 1
                    x2 -= 1
                    if x2 == b:
                        x2 -= 1
                    break;
                x2 -= 1
                if x2 == b:
                    x2 -= 1
            x1 += 1
            if x1 == a:
                x1 += 1
        print(t)

if __name__ == "__main__":
    exec()

Submission status: Time Limit Exceeded

Solution code:
Q=int(input())
for i in range(Q):
    x,y=list(map(int,input().split()))
    c=x*y-1
    z={}
    z[0]=y
    for i in range(1,x):
        j=c//i
        if j not in z.values():
            z[i]=j
    for i in range(x+1,c+1):
        j=c//i
        if j not in z.values():
            z[i]=j

    print(len(z)-1)

Submission status: Time Limit Exceeded

Solution code:
q = int(input())

for i in range(q):
    count = 0
    a, b = map(int, input().split())
    s = set()
    s.add(b)

    score = a * b
    for j in range(1, score):
        if j != a:
            num = score // j
            while num >= 1:
                if num * j < score and num not in s:
                    s.add(num)
                    count += 1
                    break
                else:
                    num -= 1
    print(count)

Submission status: Accepted

Solution code:
Q = int(input())

def derive_k(n):#n/k - n/(k+1) >= 1となる最大のkを求める。ただしn>=2
  if n == 1:
    return 0
  lt = 1
  rt = n
  while rt - lt > 1:
    ct = (lt + rt) // 2
    if n >= ct * (ct+1):
      lt = ct
    else:
      rt = ct
  return lt  
  
for _ in range(Q):
  A, B = map(int,input().split())
  k = derive_k(A*B) #A*B/k - A*B/(k+1) >= 1となる最大のkを求める
  ans = k + (A*B-1)//(k+1) - 1
  #print(A, B, k, (A*B-1)//(k+1))
  if k+1 == A and k*(k+1) < A*B:
    ans += 1
  print(ans)

Submission status: Accepted

Solution code:
q=int(input())
ab=[list(map(int,input().split())) for _ in range(q)]
from math import floor
for a,b in ab:
    # a*bをぎりぎりまで攻めたい
    # (1,1)とかはもったいない。(1,a*b-1)は良い。片方は√a*b未満で、片方は√a*bより大きい組み合わせ。
    # a==bならa未満の整数yについて適切な数字xを選べばy*x<a*bとできる。xは他のxと被らないように選択できる。
    if a==b:
        print(2*a-2)
    else:
        # t,t+1 組み合わせの積がa*bで抑えられているかどうか。(t+1)*(t+1)は必ずa*bを超える。
        # t未満の自然数については適切な整数を選べばa*b以下にできる。
        t=floor((a*b)**0.5)
        # (1,2*t-1),(2,2*t-2),(3,(a*b-1)//3),...,(t-1,(a*b-1)//(t-1))
        if t*t>=a*b: 
            # (t,t),(t,t+1)はだめ。この条件を満たすのはt*t=a*b、a!=bのときのみ。t未満の数字と適切な数字を選べばよいが、t未満の数字の内一つはaなので、その分を引く。
            print(2*t-3)
        elif t*(t+1)>=a*b: 
            # (t,t)はOK。(t,t+1)はだめ。(t,t)をまず選ぶ。t未満の数字と適切な数字を選べばよいが、t未満の数字の内一つはaなので、その分を引く。
            print(2*t-2)
        else:
            # t*tもt*(t+1)もOK。(t,t+1),(t+1,t)をまず選ぶ。あとはt未満の数字と適切な数字を選べばよいが、t未満の数字の内一つはaなので、その分を引く。
            print(2*t-1)

Submission status: Accepted

Solution code:
def is_ok(x,n):
  if x**2<=n:
    return True
  else:
    return False

def meguru_bisect(ng, ok,n):
  while (abs(ok - ng) > 1):
    mid = (ok + ng) // 2
    if is_ok(mid,n):
      ok = mid
    else:
      ng = mid
  return ok

def sqrt(n):
  return meguru_bisect(n,1,n)

Q = int(input())
for _ in range(Q):
  A,B  = list(map(int,input().split()))
  score = A*B-1
  maxA = score//(B+1)
  maxB = score//(A+1)
  crit = sqrt(score)
  ans = 0
  if maxA:
    if crit<maxA:
      ans += crit+(score//(crit+1)-score//maxA)+1
    else:
      ans += maxA
  if maxB:
    if crit<maxB:
      ans += crit+(score//(crit+1)-score//maxB)+1
    else:
      ans += maxB
  print(ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

#############
# Libraries #
#############

import sys
input = sys.stdin.readline

import math
#from math import gcd
import bisect
import heapq
from collections import defaultdict
from collections import deque
from collections import Counter
from functools import lru_cache

#############
# Constants #
#############

MOD = 10**9+7
INF = float('inf')
AZ = "abcdefghijklmnopqrstuvwxyz"

#############
# Functions #
#############

######INPUT######
def I(): return int(input().strip())
def S(): return input().strip()
def IL(): return list(map(int,input().split()))
def SL(): return list(map(str,input().split()))
def ILs(n): return list(int(input()) for _ in range(n))
def SLs(n): return list(input().strip() for _ in range(n))
def ILL(n): return [list(map(int, input().split())) for _ in range(n)]
def SLL(n): return [list(map(str, input().split())) for _ in range(n)]


#####Shorten#####
def DD(arg): return defaultdict(arg)

#####Inverse#####
def inv(n): return pow(n, MOD-2, MOD)

######Combination######
kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n): return kaijo_memo[n]
  if(len(kaijo_memo) == 0): kaijo_memo.append(1)
  while(len(kaijo_memo) <= n): kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n): return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0): gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n): gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if n == r: return 1
  if n < r or r < 0: return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret

######Factorization######
def factorization(n):
  arr = []
  temp = n
  for i in range(2, int(-(-n**0.5//1))+1):
    if temp%i==0:
      cnt=0
      while temp%i==0: 
        cnt+=1 
        temp //= i
      arr.append([i, cnt])
  if temp!=1: arr.append([temp, 1])
  if arr==[]: arr.append([n, 1])
  return arr

#####MakeDivisors######
def make_divisors(n):
  divisors = []
  for i in range(1, int(n**0.5)+1):
    if n % i == 0:
      divisors.append(i)
      if i != n // i: 
        divisors.append(n//i)
  return divisors

#####MakePrimes######
def make_primes(N):
  max = int(math.sqrt(N))
  seachList = [i for i in range(2,N+1)]
  primeNum = []
  while seachList[0] <= max:
    primeNum.append(seachList[0])
    tmp = seachList[0]
    seachList = [i for i in seachList if i % tmp != 0]
  primeNum.extend(seachList)
  return primeNum

#####GCD#####
def gcd(a, b):
    while b: a, b = b, a % b
    return a

#####LCM#####
def lcm(a, b):
    return a * b // gcd (a, b)

#####BitCount#####
def count_bit(n):
  count = 0
  while n:
    n &= n-1
    count += 1
  return count

#####ChangeBase#####
def base_10_to_n(X, n):
  if X//n: return base_10_to_n(X//n, n)+[X%n]
  return [X%n]

def base_n_to_10(X, n):
  return sum(int(str(X)[-i-1])*n**i for i in range(len(str(X))))

def base_10_to_n_without_0(X, n):
  X -= 1
  if X//n: return base_10_to_n_without_0(X//n, n)+[X%n]
  return [X%n]

#####IntLog#####
def int_log(n, a):
  count = 0
  while n>=a:
    n //= a
    count += 1
  return count

#############
# Main Code #
#############

def is_ok(x,n):
  if x**2<=n:
    return True
  else:
    return False

def meguru_bisect(ng, ok,n):
  while (abs(ok - ng) > 1):
    mid = (ok + ng) // 2
    if is_ok(mid,n):
      ok = mid
    else:
      ng = mid
  return ok

def sqrt(n):
  return meguru_bisect(n,1,n)

Q = I()
for _ in range(Q):
  A,B  = IL()
  score = A*B
  maxA = (score-1)//(B+1)
  maxB = (score-1)//(A+1)
  crit = sqrt(score-1)
  ans = 0
  if maxA:
    if crit<maxA:
      ans += crit+((score-1)//(crit+1)-(score-1)//maxA)+1
    else:
      ans += maxA
  if maxB:
    if crit<maxB:
      ans += crit+((score-1)//(crit+1)-(score-1)//maxB)+1
    else:
      ans += maxB
  print(ans)

Submission status: Accepted

Solution code:
def main():
    from sys import stdin
    def input():
        return stdin.readline().strip()

    # return max({i | i*i < a*b})
    # binary search
    def square_range(a, b):
        left = a
        right = b - 1
        while left < right:
            center = (left + right + 1) // 2
            if center * center < a * b:
                left = center
            else:
                right = center - 1
        return left

    q = int(input())
    ans = [0] * q

    for lap in range(q):
        a, b = map(int, input().split())

        if a < b:
            mid = square_range(a, b)
        else:
            mid = square_range(b, a)

        if mid * (mid + 1) < a * b:
            ans[lap] = (2 * mid - 1)
        else:
            ans[lap] = (2 * mid - 2)
    
    for i in ans:
        print(i)

main()

Submission status: Accepted

Solution code:
for q in range(int(input())):
  A,B = sorted(map(int,input().split()))
  if B-A<=1:
    print(2*A-2)
  else:
    X = int((A*B)**.5)
    X -= A*B == X*X
    print(2*X-1-(X*(X+1)>=A*B))

Submission status: Accepted

Solution code:
#!/usr/bin/env python3

import math

q = int(input())
ab = [list(map(int, input().split())) for i in range(q)]

for a, b in ab:
    if a == b:
        print((a-1)*2)
        continue

    value = int((a*b)**0.5)

    if value**2 == a*b:
        ans = value*2-3
        # print(value, ans, 1)
    elif value*(value+1) >= a*b:
        ans = value*2-2
        # print(value, ans, 2)
    else:
        ans = value*2-1
        # print(value, ans, 3)
    print(ans)

Submission status: Accepted

Solution code:
import bisect, copy, heapq, math, sys
from collections import *
from functools import lru_cache
from itertools import accumulate, combinations, permutations, product
def input():
    return sys.stdin.readline()[:-1]
def ruiseki(lst):
    return [0]+list(accumulate(lst))
def celi(a,b):
    return -(-a//b)
sys.setrecursionlimit(5000000)
mod=pow(10,9)+7
al=[chr(ord('a') + i) for i in range(26)]
direction=[[1,0],[0,1],[-1,0],[0,-1]]

q=int(input())
ab=[list(map(int,input().split())) for i in range(q)]

for i,j in ab:
    i,j=min(i,j),max(i,j)
    if i==j:
        print(2*i-2)
    elif i+1==j:
        print(2*i-2)
    else:
        ne=int((i*j)**0.5)
        if ne*ne==i*j:
            ne-=1
        if ne*(ne+1)>=i*j:
            print(2*ne-2)
        else:
            print(2*ne-1)

Submission status: Accepted

Solution code:
import sys
def I(): return int(sys.stdin.readline().rstrip())
def MI(): return map(int,sys.stdin.readline().rstrip().split())


def g(c):  # i*(i+1) <= c たる最大のiを返す
    left = 0  # ok
    right = c  # ng
    while left + 1 < right:
        mid = (left + right)//2
        if mid*(mid+1) <= c:
            left = mid
        else:
            right = mid
    return left


def query(a,b):
    if a == b:
        return a+b-2
    if a > b:
        a,b = b,a
    i0 = g(a*b)
    return i0+(a*b-1)//(i0+1)-1


Q = I()
for i in range(Q):
    a,b = MI()
    print(query(a,b))

Submission status: Accepted

Solution code:
from math import sqrt
N=int(input())
for i in range(N):
    A,B=map(int,input().split())
    if A==B:
        print(2*(A-1))
    else:
        if A>B:
            A,B=B,A
        s=int(sqrt(A*B-1))+5
        for j in range(s,s-10,-1):
            if j**2<A*B:
                s=j
                break
        a=s*2-1
        if s*(s+1)>=A*B:
            a-=1
        print(a)

Submission status: Accepted

Solution code:
from math import sqrt
Q=int(input())
for i in range(Q):
    A,B=map(int,input().split())
    if A==B:
        print(2*(A-1))
        continue
    t=A*B
    s=int(sqrt(t))+5
    for j in range(s,s-10,-1):
        if j**2<t:
            s=j
            break
    if s*(s+1)<t:
        print(s*2-1)
    else:
        print(s*2-2)

Submission status: Accepted

Solution code:
import math


def solve(A, B):
    A, B = min(A, B), max(A, B)
    if B - A <= 1:
        return 2 * A - 2
    C = math.floor(math.sqrt(A * B)) - 1
    while (C + 1) ** 2 < A * B:
        C += 1
    if C * (C + 1) >= A * B:
        return 2 * C - 2
    else:
        return 2 * C - 1


def main():
    Q = int(input())
    query_list = [list(map(int, input().split())) for _ in range(Q)]
    ans = [solve(a, b) for a, b in query_list]
    for a in ans:
        print(a)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
'''
研究室PCでの解答
'''
import math
#import numpy as np
import queue
import bisect
from collections import deque,defaultdict
import heapq as hpq
from sys import stdin,setrecursionlimit
#from scipy.sparse.csgraph import dijkstra
#from scipy.sparse import csr_matrix
ipt = stdin.readline
setrecursionlimit(10**7)
mod = 10**9+7 #998244353
dir = [(-1,0),(1,0),(0,-1),(0,1)]
alp = "abcdefghijklmnopqrstuvwxyz"


def main():
    q = int(ipt())
    for _ in range(q):
        a,b = map(int,ipt().split())
        if a > b:
            a,b = b,a
        tgt = a*b
        rt = int(tgt**0.5+0.0000000000001)
        ans = rt*2-1
        if a == b:
            ans -= 1
        elif rt**2 == tgt:
            ans -= 2
        elif rt*(rt+1) < tgt:
            pass
        elif rt**2-1 < tgt:
            ans -= 1
        print(ans)

    return None

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys,heapq
input = sys.stdin.buffer.readline

Q = int(input())

def f(x,y):
    ma = x*y - 1
    ok = 0
    ng = 10**9 + 1
    while ng - ok > 1:
        mid = (ok+ng)//2
        if mid**2 <= ma:
            ok = mid
        else:
            ng = mid
    return ok

ans = []
for testcase in range(Q):
    a,b = map(int,input().split())
    if a == 1 and b == 1:
        ans.append(0)
        continue
    p = f(a,b)
    res = p*2
    if a != b:
        res -= 1
    if p == (a*b - 1)//p:
        res -= 1
    ans.append(res)

print(*ans,sep='\n')

Submission status: Accepted

Solution code:
for _ in range(int(input())):
  a,b=map(int,input().split())
  if abs(a-b)<=1:print(min(a,b)*2-2)
  else:
    c=int((a*b)**0.5)
    if c**2==a*b:c-=1
    if c*(c+1)>=a*b:print(2*c-2)
    else:print(2*c-1)

Submission status: Accepted

Solution code:
import sys
import math
def input(): return sys.stdin.readline().rstrip()


def solve(x, y):
    if x == y:
        return 2*x-2
    else:
        k = x*y
        sqr = math.ceil(math.sqrt(k))-1
        return 2*sqr-2+(sqr*(sqr+1) < k)


def main():
    q=int(input())
    for _ in range(q):
        a,b=map(int, input().split())
        print(solve(a,b))



if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
import math
def input(): return sys.stdin.readline().rstrip()


def solve(x, y):
    if x == y:
        return 2*x-2
    elif abs(x-y)==1:
        return min(x,y)*2-2
    else:
        k = x*y
        sqr = math.ceil(math.sqrt(k))-1
        return 2*sqr-2+(sqr*(sqr+1) < k)


def main():
    q=int(input())
    for _ in range(q):
        a,b=map(int, input().split())
        print(solve(a,b))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
Q=int(input())
AB=[list(map(int,input().split())) for i in range(Q)]
for a,b in AB:
    x=int((a*b)**.5)
    if x*x==a*b:
        x-=1
    if max(a,b)-min(a,b)<2:
        print(2*min(a,b)-2)
    elif a*b<=x*(x+1):
        print(2*x-2)
    else:
        print(2*x-1)

Submission status: Accepted

Solution code:
import math
Q=int(input())
for _ in range(Q):
  A,B=map(int,input().split())
  if abs(A-B)<2:
    print(min(A,B)*2-2)
  else:
    s=int(math.ceil(math.sqrt(A*B)))-1
    if s**2+s<A*B:
      print(2*s-1)
    else:
      print(2*s-2)

Submission status: Accepted

Solution code:
from math import sqrt

def main():
    q = int(input())
    ans = [None]*q
    for i in range(q):
        a, b = map(int, input().split())
        score = a*b
        tmp = 0
        if b < a:
            a, b = b, a
        if a == b:
            tmp = (a-1) + (b-1)
        elif a+1 == b:
            tmp = (a-1) + (a-1)
        else:
            p = int(sqrt(score))
            if p**2 == score:
                p -= 1
            tmp = 2*p - 1
            if p * (p+1) >= score:
                tmp -= 1
        ans[i] = tmp
    for v in ans:
        print(v)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import math
q=int(input())
for i in range(q):
 a,b=map(int,input().split())
 if abs(a-b)<2:print(min(a,b)*2-2)
 else:
  s=int(math.ceil(math.sqrt(a*b)))-1
  if s**2+s<a*b:print(2*s-1)
  else:print(2*s-2)

Submission status: Accepted

Solution code:
for a in[*open(0)][1:]:a,b=map(int,a.split());c=int((a*b)**.5);print((a*b-(a!=b))//c+c-2)

Submission status: Accepted

Solution code:
for a in[*open(0)][1:]:a,b=map(int,a.split());c=a*b;d=int(c**.5);print(~(d*-~d>=c)+d+d-(c==d*d>0<a!=b))

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
Q = int(input())
AB = [list(map(int,input().split())) for i in range(Q)]

small_case = {(1,1):0, (1,2):0}
for A,B in AB:
    M = A*B
    A,B = sorted([A,B])
    if (A,B) in small_case:
        print(small_case[(A,B)])
        continue
    ans = 0
    i = 1
    b = int(pow(M,0.5))
    if b == B:
        b -= 1
    ans += (M-1)//b - A
    ans += b-1
    ans += A-1
    print(ans)

Submission status: Accepted

Solution code:
def main():
    n = int(input())
    for _ in range(n):
        a, b = map(int, input().split())
        ref = a * b - 1
        rng = int(ref ** 0.5) - 2
        while rng ** 2 < a * b:
            rng += 1
        rng -= 1
        if a == b or abs(a - b) == 1:
            print(2 * min(a, b) - 2)
        elif rng * (rng + 1) >= a * b:
            print(2 * rng - 2)
        else:
            print(2 * rng - 1)
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
def input(): return sys.stdin.readline().strip()


def prod_max(a, d, b, e, n):
    """
    初項a、公差dの等差数列および初項b、公差eの等差数列を各項ごとに
    掛け合わせた時の第0項から第n項までの最大値を返す。
    a>0, d>0, b>0, e<0を仮定する。
    """
    if n < 0: return 0
    idx = round((-(b / e) - (a / d)) / 2)
    if idx < 0: return a * b
    if idx <= n: return (a + idx * d) * (b + idx * e)
    return (a + n * d) * (b + n * e)

def main():
    """
    解説放送にしたがって決め打ち二分探索による実装。
    まずa<=bを仮定しても良い。a*bよりも小さい積がX個作れるかを考える。
    これは1, 2, ..., a-1, a+1, ...からX個、1, 2, ..., b-1, b+1, ...からX個選んで
    小さいものと大きいもののペアで積を取ったものが全てa*b未満であることをいえば良い。

    積を実際に全て計算していては間に合わないが、実質これは等差数列の積なので
    これらの積のうち最大値はO(1)で計算可能。
    """
    Q = int(input())
    for _ in range(Q):
        a, b = map(int, input().split())
        if a > b: a, b = b, a

        # 決め打ち二分探索
        left = a - 1
        right = 10 ** 10
        while right - left > 1:
            mid = (left + right) // 2
            if mid < b:
                """
                この時ペアリングは
                1*mid, 2*(mid-1), ..., (a-1)*(mid-a+1), (a+1)*(mid-a), ..., (mid+1)*1
                前半後半でそれぞれ最大値を取得する。
                """
                cand1 = prod_max(1, 1, mid, -1, a-2)
                cand2 = prod_max(a+1, 1, mid-a+1, -1, mid-a)
                if cand1 < a * b and cand2 < a * b: left = mid
                else: right = mid
                #print("case1 left={}, right={}".format(left, right))
            elif mid < a + b - 1:
                """
                この時ペアリングは
                1*(mid+1), 2*mid, ..., (mid-b+1)*(b+1),
                (mid-b+2)*(b-1), ..., (a-1)*(mid-a+2),
                (a+1)*(mid-a+1), ..., (mid+1)*1
                より3つに分けて最大値を求める。
                """
                cand1 = prod_max(1, 1, mid+1, -1, mid-b)
                cand2 = prod_max(mid-b+2, 1, b-1, -1, a+b-mid-3)
                cand3 = prod_max(a+1, 1, mid-a+1, -1, mid-a)
                if cand1 < a * b and cand2 < a * b and cand3 < a * b: left = mid
                else: right = mid
                #print("case2 left={}, right={}".format(left, right))
            else:
                """
                この時ペアリングは
                1*(mid+1), 2*mid, ..., (mid-a+3)*(a-1),
                (a+1)*(mid-a+2), ..., (mid-b+2)*(b+1),
                (mid-b+3)*(b-1), ..., (mid+1)*1
                より3つに分けて最大値を求める。
                """
                cand1 = prod_max(1, 1, mid+1, -1, a-2)
                cand2 = prod_max(a+1, 1, mid-a+2, -1, mid-a-b+1)
                cand3 = prod_max(mid-b+3, 1, b-1, -1, b-2)
                if cand1 < a * b and cand2 < a * b and cand3 < a * b: left = mid
                else: right = mid
                #print("case3 left={}, right={}".format(left, right))
        print(left)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from decimal import *
Q = int(input())#100

for i in range(Q):
  a, b = map(int, input().split())
  a = Decimal(a)
  b = Decimal(b)
  m = int((Decimal(a * b) - 1) ** Decimal(1 / 2))
  ans = 2 * m
  if a == b:
    ans -= 0
  else:
    if int((Decimal(a * b) - Decimal(1)) / Decimal(m)) == m:
      ans -= 2
    else:
      ans -= 1
  print(ans)

Submission status: Accepted

Solution code:
q=int(input())
for _ in range(q):
    a_,b_=map(int,input().split())
    a=min(a_,b_)
    b=max(a_,b_)
    ng=b+1
    ok=1
    while ng-ok>1:
        mid=(ok+ng)//2
        m=-(-(a+mid)//2)
        if m==a:
          m-=1
        if (a+mid-m)*m<a*b:
            ok=mid
        else:
            ng=mid
    print(a+ok-2)

Submission status: Accepted

Solution code:
from math import floor
q = int(input())
ab=[list(map(int,input().split())) for _ in range(q)]
for a,b in ab:
    if a==b:
        print(2*a-2)
        continue
    t = floor((a*b)**0.5)
    if t*t >=a*b:
        print(2*t-3)
    elif t*(t+1)>=a*b:
        print(2*t-2)
    else:
        print(2*t-1)