分治算法, 递归实现

递推应该也是可以的, 只是递归更容易写.
基本上和教材里面的一模一样, 区别在于保存了递归的结果, 因为有很多组数据, 我猜会有大量重复的计算.

时间复杂度

对于每一组数据, 递归深度为N, 每个递归的分支只有一个, 因此, 时间复杂度是O(N)

参考文献

<算法竞赛进阶指南>

Python 代码

# %% 
from functools import lru_cache

#%%
@lru_cache(None)
def cal(N, M):
    if N == 0:
        return 0, 0
    Len = 1 << (N - 1)
    cnt = 1 << (2 * (N - 1))
    d, m = divmod(M, cnt)
    x, y = cal(N - 1, m)
    if d == 0:
        return y, x
    elif d == 1:
        return x, y + Len
    elif d == 2:
        return x + Len, y + Len
    else:
        return 2 * Len - 1 - y, Len - 1 - x


def solve(N, A, B):
    xA, yA = cal(N, A)
    xB, yB = cal(N, B)
    return int(0.5 + 10 * ((xA - xB) ** 2 + (yA - yB) ** 2) ** 0.5)    


#%%
T = int(input())
for _ in range(T):
    N, A, B = map(int, input().split())
    print(solve(N, A - 1, B - 1))