def test_all(f):
for i, data in enumerate(eval(f'test_data{f.__name__[0]}')):
exp = data["out"]
ans = f(*data["in"])
result = "AC" if exp == ans else "WA"
print(f"{i+1} {result}: expected: {exp}, output: {ans}")
from math import ceil, sqrt
def C(N):
a = [0] * N
a[1] = 1
for i in range(2, N):
for j in range(1, ceil(sqrt(i))):
if i % j == 0: a[i] += 1
a[i] *= 2
if int(sqrt(i)) ** 2 == i: a[i] += 1
# print(a)
ans = 0
for i in range(1, N):
ans += a[i] * a[N - i]
return anstest_all(C)
import numpy as np
def C(N):
a = np.ones(N, dtype=int)
for i in range(2, N):
sli = slice(i, N, i)
a[sli] += 1
a = a[1:]
return sum(a * a[::-1])test_all(C)
from enum import Enum
from functools import lru_cache, reduce
from operator import mul
from itertools import product
class Sieve:
method = Enum("method", ["ERATOSTHENES", "LINEAR"])
def __init__(self, n, method=method.ERATOSTHENES):
if method == self.method.ERATOSTHENES:
primes = [False, False] + [True] * (n - 1)
self.lpf = list(range(n + 1))
for p in range(2, int(n ** (1 / 2)) + 1):
if not primes[p]: continue
self.lpf[p] = p
for q in range(p * 2, n + 1, p):
primes[q] = False
if self.lpf[q] == q: self.lpf[q] = p
elif method == self.method.LINEAR:
self.lpf = list(range(n + 1))
primes = []
for i in range(2, n + 1):
if self.lpf[i] == i:
primes.append(i)
lpf_i = self.lpf[i]
for p in primes:
if p > lpf_i or i * p > n: break
self.lpf[i * p] = p
else:
raise ValueError(f"'method' must be instance of '{self.__class__.__name__}.method'.")
# 各iがlpf(i)で何回割り切れるか
self.lpf_e = [[1, 0] for _ in range(n + 1)]
for i in range(2, n + 1):
p = self.lpf[i]
j = i // p
self.lpf_e[i] = (
[self.lpf_e[j][0] * p, self.lpf_e[j][1] + 1]
if self.lpf[j] == p else
[self.lpf[i], 1]
)
@lru_cache(None)
def factors(self, n):
lpfs = [(self.lpf[n], self.lpf_e[n][1])]
if self.lpf_e[n][0] == n:
return lpfs
else:
return lpfs + self.factors(n // self.lpf_e[n][0])
@lru_cache(None)
def divisors(self, n):
if n == 1:
return [1]
elif self.lpf[n] == n:
return [1, n]
else:
return sorted([
a * b for a, b
in product(
self.divisors(n // self.lpf_e[n][0]),
[self.lpf[n] ** i for i in range(self.lpf_e[n][1] + 1)]
)
])
def divisors_count(self, n):
return reduce(mul, [e + 1 for _, e in self.factors(n)])
def C(N):
s = Sieve(N)
return sum(s.divisors_count(N - i) * s.divisors_count(i) for i in range(1, N))test_all(C)
from collections import defaultdict
class DSU():
def __init__(self, n=None):
self.dsu = defaultdict(lambda: -1)
if n:
for i in range(n): self.dsu[i]
def leader(self, i):
if self.dsu[i] < 0: return i
self.dsu[i] = self.leader(self.dsu[i])
return self.dsu[i]
def merge(self, i, j):
'''サイズの大きい方(x)に小さい方(y)をマージ'''
if i == j: return
x = self.leader(i)
y = self.leader(j)
if x == y: return
if self.dsu[x] > self.dsu[y]: x, y = y, x
self.dsu[x] += self.dsu[y]
self.dsu[y] = x
def members(self, i):
l = self.leader(i)
return [k for k, v in self.dsu.items() if self.leader(k) == l]
def __len__(self):
return len([1 for v in self.dsu.values() if v < 0])def D(N, M, uv):
dsu = DSU(N + 1)
for i in uv:
dsu.merge(*i)
edge = defaultdict(int)
for u, v in uv:
edge[dsu.leader(u)] += 1
for l, e in edge.items():
if abs(dsu.dsu[l]) != e: return "No"
return "Yes" if len(uv) == N else "No"test_all(D)
from collections import defaultdict
class DSU():
def __init__(self, n=None):
self.dsu = defaultdict(lambda: -1)
if n:
for i in range(n): self.dsu[i]
def leader(self, i):
if self.dsu[i] < 0: return i
self.dsu[i] = self.leader(self.dsu[i])
return self.dsu[i]
def merge(self, i, j):
'''サイズの大きい方(x)に小さい方(y)をマージ'''
# if i == j: return
x = self.leader(i)
y = self.leader(j)
if x == y: return True
if self.dsu[x] > self.dsu[y]: x, y = y, x
self.dsu[x] += self.dsu[y]
self.dsu[y] = x
def members(self, i):
l = self.leader(i)
return [k for k, v in self.dsu.items() if self.leader(k) == l]
def __len__(self):
return len([1 for v in self.dsu.values() if v < 0])def D(N, M, uv):
dsu = DSU(N + 1)
for u, v in uv:
if dsu.merge(u, v): dsu.merge(0, u)
return "Yes" if N == M and abs(dsu.dsu[dsu.leader(0)]) == N + 1 else "No"test_all(D)
from collections import defaultdict, deque
def E(N, M, uv):
nxt = set()
edge = defaultdict(list)
for u, v in uv:
edge[u].append(v)
nxt.add(v)
ans = 0
for a in range(1, N + 1):
q = deque(edge[a])
while q:
b = q.popleft()
if b == a: continue
for c in edge[b]:
if c in [a, b]: continue
if c not in edge[a]:
ans += 1
edge[a].append(c)
q.append(c)
# print(a, b, c)
return anstest_all(E)
from collections import defaultdict, deque
def E(N, M, uv):
edge = defaultdict(set)
for u, v in uv:
edge[u].add(v)
ans = 0
for i in range(1, N + 1):
q = deque(edge[i])
seen = edge[i].copy()
seen.add(i)
while q:
now = q.popleft()
for nxt in edge[now]:
if nxt in seen: continue
q.append(nxt)
seen.add(nxt)
ans += len(seen) - 1 - len(edge[i])
return anstest_all(E)
AtCoder Inc.
