デンソークリエイトプログラミングコンテスト2024（AtCoder Beginner Contest 361）F,G問題メモ

def get_root_k(n, k):
    a = int(pow(n, 1 / k))
    while pow(a, k) > n:
        a -= 1
    while pow(a + 1, k) <= n:
        a += 1
    return a


def customized_mobius(n):
    """
    約数包除用メビウス関数
             ┌ i が相異なる奇数個の素数の積で表されるとき 1
    res[i] = ┼ i が相異なる偶数個の素数の積で表されるとき -1
             └ それ以外（i=0,1含む）

    数え上げにおいて何らかのパラメータ k を固定した答えを f(k) として
     f(2) と f(3) を個別に求めると公倍数の f(6) が重複してしまう場合などは、
    Σ_k (f(k) * res[k]) を求めると、包除原理の要領で重複が除ける。
    """
    table = list(range(n + 1))
    for i in range(2, int(n ** 0.5) + 1):
        if table[i] == i:
            for j in range(i * i, n + 1, i):
                table[j] = i
            for j in range(i * i, n + 1, i * i):
                table[j] = 0
    res = [0] * (n + 1)
    res[1] = -1
    for i in range(2, n + 1):
        if table[i] == 0:
            continue
        res[i] = -res[i // table[i]]
    res[0] = res[1] = 0
    return res


def is_square(x):
    y = int(x ** 0.5)
    return y * y == x


n = int(input())
moebius = customized_mobius(60)

ans = 0
for p in range(1, 60):
    if moebius[p] != 0:
        ans += get_root_k(n, p) * moebius[p]
ans -= 1
print(ans)

class UnionFind:
    def __init__(self, n):
        self.table = [-1] * n

    def root(self, x):
        stack = []
        tbl = self.table
        while tbl[x] >= 0:
            stack.append(x)
            x = tbl[x]
        for y in stack:
            tbl[y] = x
        return x

    def find(self, x, y):
        return self.root(x) == self.root(y)

    def unite(self, x, y):
        r1 = self.root(x)
        r2 = self.root(y)
        if r1 == r2:
            return False
        d1 = self.table[r1]
        d2 = self.table[r2]
        if d1 <= d2:
            self.table[r2] = r1
            self.table[r1] += d2
        else:
            self.table[r1] = r2
            self.table[r2] += d1
        return True

    def get_size(self, x):
        return -self.table[self.root(x)]


n = int(input())
MAX_COORD = 200_002

points = [[] for _ in range(MAX_COORD + 1)]
for _ in range(n):
    x, y = map(int, input().split())
    x += 1
    y += 1
    points[x].append(y)

sections = []
sizes = []
idx = 0
for x in range(MAX_COORD + 1):
    yyy = points[x]
    yyy.sort()
    cur_section = []
    l = 0
    for y in yyy:
        if l == y:
            l += 1
            continue
        cur_section.append((l, y - 1, idx))
        sizes.append(y - l)
        idx += 1
        l = y + 1
    cur_section.append((l, MAX_COORD, idx))
    sizes.append(MAX_COORD - l + 1)
    idx += 1
    sections.append(cur_section)

uft = UnionFind(idx)
for x in range(MAX_COORD):
    s1 = sections[x]
    s2 = sections[x + 1]
    i = 0
    j = 0
    while i < len(s1) and j < len(s2):
        if s1[i][0] > s2[j][1]:
            j += 1
        elif s1[i][1] < s2[j][0]:
            i += 1
        else:
            uft.unite(s1[i][2], s2[j][2])
            if s1[i][1] == s2[j][1]:
                i += 1
                j += 1
            elif s1[i][1] < s2[j][1]:
                i += 1
            else:
                j += 1

ans = 0
out_group = uft.root(0)
for i in range(1, idx):
    if uft.root(i) != out_group:
        ans += sizes[i]
print(ans)