メビウス関数を知っていれば楽に解ける問題。
$b$ を決めれば、$a=1~ \lfloor \sqrt[b]{N} \rfloor$ が全て条件を満たすので、
基本的な方針としては、様々な $b$ に対して $\lfloor \sqrt[b]{N} \rfloor$ を足し合わせたものが答えとなる。
(以降、単に $\sqrt[b]{N}$ で、$\lfloor \sqrt[b]{N} \rfloor$ を指すとする)
$b$ として取り得る値は、$2^{60} \gt 10^{18}$ より、$2~59$ を考えればよい。
また $b$ が素数で無い場合、$b=kb'$ と2数の積に分解できるとして、
$a^b=(a^k)^{b'}$ と、より小さい指数による表現ができてしまうので $b$ は素数のみ考えればよい。
しかし、$4^3 = 8^2 = 64$ など、異なる $(a,b)$ が同じ $x$ になってしまうことがある。
これは、$(2^2)^3=(2^3)^2$ のように、$a$ 自体が $c^d$ と表せる場合に発生しうる。
$b=2$ でも $b=3$ でも表せてしまう数は、$b=6$ でも表せるので、
$\sqrt[2]{N}$ + $\sqrt[3]{N}$ - $\sqrt[6]{N}$ とすれば重複を除けることになる。
このような事をするのに便利なのが、メビウス関数(を、約数系包除原理用にカスタマイズしたもの)である。
これで、$\displaystyle \sum_{b=2}^{59} \tilde{\mu}(b) \times \sqrt[b]{N}$ が答えとなる。
(なんか、1だけずれるので、微調整したら通る)
Python3
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)
ご丁寧に、サンプルに $N$ が最大の $10^{18}$ のときがあって、答えは $10^{9}+10^{6}+\alpha$ 程度である。
このうち $a^2$ と表せる数が $10^9$ 個あるので、残りは $10^6+\alpha$ 個程度である。
つまり、$3$ 以上の素数の $b$ と、$\sqrt[b]{N}$ 以下の $a$ について、
素直に $a^b$ を計算して set(重複しない集合を表現するデータ構造)に放り込んでいっても、
対象は $10^6$ 個程度であり、TLEやMLEにはならないことがわかる。
重複除外はsetの機能に任せてよくなり、(最終的なsetのサイズ + $\sqrt[2]{N}$)が答えとなる。
ただし、$a=c^2$ と表現されるような $a$ は、$\sqrt[2]{N}$ の方で数えられているので、$a$ が平方数の場合は除外する。
ひたすら泥臭く頑張ればできるのはできるんだけど、なかなか上手く実装するのが難しい問題。
公式Editorialを自分用にメモしただけ。なるほど!この発想は気がつかなかった。
「石の置かれていない格子点」を空格子点とする。
この問題は、愚直には、範囲内の隣り合う空格子点同士をUnion-Findで結ぶなどすることで、
外 $(-1,-1)$ と同じグループにならない空格子点の個数を数えればよい。
ただ、$O(X_{max}Y_{max})$ の頂点ができるので、TLEとなる。
考慮する空格子点を石の周囲最大8つに限定すると、石により分断されているかの判定ができる情報量を保ったまま、頂点数を $O(N)$ とできる。
しかし、どっちが内か外かの判定や、入れ子構造になった場合を見つけて除外するのに、地道な実装が必要となる。(公式Editorial 1つめの解法)
Union-Find上の頂点数を減らすもう1つの方法として、
互いに行き来できることが明らかな空格子点のカタマリは、まとめてやることが考えられる。
具体的には、横に連続する空格子点のカタマリは、1つの頂点としてまとめる。
|-----------------------------
|--|■■■■■||■■|---------
||■|--------|■|--|■|-------
||■|----------------|■|-----
||■|--|■■|------|■|-------
|--|■■|--|■■■■|---------
|-----------------------------
こうすると、頂点数は $O(X_{max}+N)$ に抑えられ、愚直とほぼ同じ解法が使える。
入れ子構造とかも考えなくて済み、楽に実装できる。
外周に1個分、確実に空格子点である列を作る必要がある点に注意。
Python3
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)