AtCoder Beginner Contest 428（Promotion of AtCoderJobs）D,E,F,G問題メモ

from math import sqrt


def solve(c, d):
    def int_sqrt_ceil(x):
        res = int(sqrt(x))
        while res ** 2 < x:
            res += 1
        while (res - 1) ** 2 >= x:
            res -= 1
        return res

    def int_sqrt_floor(x):
        res = int(sqrt(x))
        while (res + 1) ** 2 <= x:
            res += 1
        while res ** 2 > x:
            res -= 1
        return res

    min_lim = len(str(c + 1))
    max_lim = len(str(c + d))
    ans = 0
    for p in range(min_lim, max_lim + 1):
        m = c * (10 ** p)
        pp = (10 ** (p - 1))
        qq = min((10 ** p) - 1, c + d)
        l = int_sqrt_ceil(m + max(c + 1, pp))
        r = int_sqrt_floor(m + qq)
        ans += max(0, r - l + 1)

    return ans


t = int(input())
for _ in range(t):
    c, d = map(int, input().split())
    ans = solve(c, d)
    print(ans)

from collections import deque


def get_tree_center(links):
    """
    木の直径と、中心の頂点番号を求める（1辺の距離を1とみなす）

    :param links: links[v] = {u1, u2, ...}  隣接する頂点番号
    :return: (Diameter, c1, c2)  直径が偶数の場合、中心は単一頂点のためc1が中心、c2=-1。奇数の場合、中心はc1-c2を結ぶ辺
    """

    n = len(links)

    # first bfs
    q = deque()
    q.append(0)
    dists = [-2] * n
    dists[0] = -1

    v = -1
    while q:
        v = q.popleft()
        for u in links[v]:
            if dists[u] != -2:
                continue
            q.append(u)
            dists[u] = -1
    v1 = v

    # second bfs
    q = deque()
    q.append(v1)
    predecessors = [-1] * n
    dists[v1] = 0

    v = -1
    while q:
        v = q.popleft()
        for u in links[v]:
            if dists[u] != -1:
                continue
            q.append(u)
            dists[u] = dists[v] + 1
            predecessors[u] = v

    v2 = v
    d = dists[v]

    if d % 2 == 0:
        hd = d // 2
        i = v2
        while i != v1:
            if dists[i] == hd:
                return d, i, -1
            i = predecessors[i]
    else:
        hd = (d + 1) // 2
        i = v2
        while i != v1:
            if dists[i] == hd:
                return d, predecessors[i], i
            i = predecessors[i]

    raise AssertionError('Not Reachable')


def solve(n, edges):
    links = [set() for _ in range(n)]
    for u, v in edges:
        u -= 1
        v -= 1
        links[u].add(v)
        links[v].add(u)

    d, c1, c2 = get_tree_center(links)
    # print(f'{d=} {c1=} {c2=}')
    max_leaf = [-1] * n
    distances = [-1] * n

    def dfs1(c, r):
        q = [c]
        distances[c] = 0
        while q:
            u = q[-1]
            if max_leaf[u] == -1:
                max_leaf[u] = -2
                for v in links[u]:
                    if max_leaf[v] == -1:
                        distances[v] = distances[u] + 1
                        q.append(v)
                continue
            q.pop()
            if distances[u] == r:
                max_leaf[u] = u
                continue
            ml = -1
            for v in links[u]:
                if max_leaf[v] < 0:
                    continue
                ml = max(ml, max_leaf[v])
            max_leaf[u] = ml

    def dfs2(s, ml):
        q = [s]
        while q:
            u = q.pop()
            ans[u] = ml
            for v in links[u]:
                if ans[v] != -1:
                    continue
                q.append(v)

    ans = [-1] * n
    if c2 == -1:
        dfs1(c1, d // 2)
        mls = [max_leaf[v] for v in links[c1]]
        mls.sort(reverse=True)
        d1, d2 = mls[:2]
        ans[c1] = d1
        for v in links[c1]:
            if max_leaf[v] == d1:
                dfs2(v, d2)
            else:
                dfs2(v, d1)
    else:
        links[c1].remove(c2)
        links[c2].remove(c1)
        dfs1(c1, d // 2)
        dfs1(c2, d // 2)
        dfs2(c1, max_leaf[c2])
        dfs2(c2, max_leaf[c1])

    ans = [a + 1 for a in ans]
    return ans


n = int(input())
edges = [tuple(map(int, input().split())) for _ in range(n - 1)]
ans = solve(n, edges)
print('\n'.join(map(str, ans)))

def solve(n, www, q, queries):
    def in_or_out(i, x):
        l = 0
        r = len(arranged)
        while l + 1 < r:
            mid = (l + r) // 2
            if arranged[mid][0] >= i:
                l = mid
            else:
                r = mid
        if arranged[l][1] == 1:
            ll = arranged[l][2]
            return ll <= x < ll + www[i]
        else:
            rr = arranged[l][2]
            return rr - www[i] <= x < rr

    buf = []
    arranged = [(1 << 60, 2, www[-1]), (n - 1, 1, 0)]
    for op, v in queries:
        if op == 1:
            v -= 1
            while arranged[-1][0] <= v:
                arranged.pop()
            if arranged[-1][1] == 1:
                continue
            r = arranged[-1][2]
            arranged.append((v, 1, r - www[v]))
        elif op == 2:
            v -= 1
            while arranged[-1][0] <= v:
                arranged.pop()
            if arranged[-1][1] == 2:
                continue
            l = arranged[-1][2]
            arranged.append((v, 2, l + www[v]))
        else:
            x = v
            if www[-1] <= x:
                buf.append(0)
                continue
            l = -1
            r = n - 1
            while l + 1 < r:
                mid = (l + r) // 2
                if in_or_out(mid, x):
                    r = mid
                else:
                    l = mid
            buf.append(n - r)

    return buf


n = int(input())
www = list(map(int, input().split()))
q = int(input())
queries = [tuple(map(int, input().split())) for _ in range(q)]
ans = solve(n, www, q, queries)
print('\n'.join(map(str, ans)))

from collections import defaultdict


def solve(n, u, bbb):
    MOD = 998244353
    invs = [0] + [pow(i, -1, MOD) for i in range(1, 21)]

    ans = [0] * (u + 1)
    raw_results = [[]]
    unq_results = [[]]
    base = [0] * (u + 1)
    for b in bbb:
        ans[b] += 1
        base[b] += 1
    raw_results.append(base)
    unq_results.append(base)

    roots = defaultdict(list)
    for i in range(2, int(u ** 0.5) + 3):
        j = i * i
        k = 2
        while j <= u:
            roots[j].append((i, k))
            j *= i
            k += 1

    for num_jewel in range(2, 20):
        prev = raw_results[-1]
        tmp = [0] * (u + 1)
        for i in range(2, u + 1):
            if base[i] == 0:
                continue
            j = 2
            while i * j <= u:
                tmp[i * j] += base[i] * prev[j]
                tmp[i * j] %= MOD
                j += 1
        if all(c == 0 for c in tmp):
            break
        raw_results.append(tmp.copy())
        for i in range(2, u + 1):
            if tmp[i] == 0:
                continue
            for p, q in roots[i]:
                if num_jewel % q != 0:
                    continue
                w = num_jewel // q
                x = unq_results[w][p]
                ans[i] += x
                ans[i] %= MOD
                tmp[i] -= x * w
            tmp[i] *= invs[num_jewel]
            tmp[i] %= MOD
            ans[i] += tmp[i]
            ans[i] %= MOD
        unq_results.append(tmp)

    return ans[2:]


n, u = map(int, input().split())
bbb = list(map(int, input().split()))
ans = solve(n, u, bbb)
print(*ans)