题解 | 小数字 | Python3

# n <= 2时执行-1操作最小，n > 2时执行开根号操作最小
# 对大数字循环执行操作很慢，会超时，所以需要优化一下
# n <= 2时，可以直接用n减去操作次数，即为结果
# n > 2时，需要计算最少多少次操作才能让n落到(-∞, 2]区间内
# 设n > 2时需要x次操作，计算边界条件，以下式子成立
# n ** (1 / (2 ** x)) <= 2
# 等价于n <= 2 ** (2 ** x)
# 式子两边取两次以2为底的对数，得到x >= math.log2(math.log2(n))
# 不等号右侧是个浮点数，需要得到的x是整数，向上取整即可，x = math.ceil(x)
# （题面要求每次开根号之后向上取整，上面求解x时并未涉及，但不影响正确性，请读者自行证明）
# 于是我们知道，对n开x次根号，即可得到2
# 这时，我们比对一下x和操作次数m的大小
# 如果m < x，则一直开根号m次即可，n = math.ceil(n ** (1 / (2 ** m)))
# 如果m >= x，则开根号x次得到2，再执行m - x次减一操作，此时可直接跳过开根号，n = 2 - (m - x)

import math


T = int(input())

for t in range(T):
    n, m = map(int, input().split())
    if n > 2:
        x = math.ceil(math.log2(math.log2(n)))
        if m < x:
            n = n ** (1 / (2 ** m))
            n = math.ceil(n)
        else:
            m = m - x
            n = 2 - m
    else:
        n = n - m
    print(n)