結果
| 問題 |
No.2645 Sum of Divisors?
|
| コンテスト | |
| ユーザー |
 shash4321
|
| 提出日時 | 2025-01-06 12:41:02 |
| 言語 | PyPy3 (7.3.15) |
| 結果 |
AC
|
| 実行時間 | 177 ms / 2,000 ms |
| コード長 | 18,386 bytes |
| コンパイル時間 | 256 ms |
| コンパイル使用メモリ | 83,100 KB |
| 実行使用メモリ | 91,616 KB |
| 最終ジャッジ日時 | 2025-01-06 12:41:10 |
| 合計ジャッジ時間 | 7,107 ms |
|
ジャッジサーバーID （参考情報） |
judge5 / judge3 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 32 |
ソースコード
import sys
from math import gcd, factorial as fact,hypot,acos,atan2,pi,ceil,sqrt,log2,isqrt,log,dist,perm,comb,prod,exp,log10,cos,sin
try: from math import lcm
except: lcm = lambda a,b: a//gcd(a,b)*b
from heapq import *
from itertools import *
try:
from functools import cache
except:
from functools import lru_cache
def cache(user_function, /):
return lru_cache(maxsize=None)(user_function)
from functools import reduce, cmp_to_key
from bisect import bisect_left, bisect_right
from collections import deque, Counter, defaultdict
from fractions import Fraction as frac
from decimal import Decimal as dec
import typing
import operator
try:
from tqdm import trange
except:
trange = range
from random import randint, randrange
# import pypyjit
# pypyjit.set_param(max_unroll_recursion=-1,vec=1)
sys.setrecursionlimit(10**5+10)
input = lambda: sys.stdin.readline().strip()
def read(fn=int):
return map(fn,input().split())
def read(*fn):
if not fn: fn = [int]
l = input().split()
if len(fn) == 1: return map(fn[0], l)
return (f(x) for f,x in zip(fn,l))
def dbg(*args,**kwargs):
print(*args,**kwargs,file=sys.stderr)
class ostream():
def __lshift__(self,s):
sys.stdout.write(str(s))
return self
cout = ostream()
endl = '\n'
yes = 'YES'
no = 'NO'
# toks = (tok for tok in sys.stdin.read().split())
# def rd(fn=int): return fn(next(toks))
# def rdn(n,fn=int): return (rd(fn) for _ in range(n))
mod = 998244353
mod = 10**9 + 7
def mul(a,b,mod=0):
if sum(map(sum,a)) == 0 or sum(map(sum,b)) == 0:
return [[0]*len(b[0]) for _ in range(len(a))]
c = [[0 for j in range(len(b[0]))] for i in range(len(a))]
for i in range(len(a)):
for k in range(len(b)):
for j in range(len(b[0])):
c[i][j] += a[i][k]*b[k][j]
if mod: c[i][j] %= mod
return c
def power(x,y,mod=0):
n = len(x)
res = [[+(i==j) for j in range(n)] for i in range(n)]
while y:
if y % 2: res = mul(res,x,mod)
x = mul(x,x,mod)
y //= 2
return res
def sieve(n):
primes = []
isp = [1] * (n+1)
isp[0] = isp[1] = 0
for i in range(2,n+1):
if isp[i]:
primes += [i]
for j in range(i*i,n+1,i):
isp[j] = 0
return primes
def eea(a,b):
if not a: return b,0,1
g,x,y = eea(b%a,a)
return g, y - (b//a)*x, x
def factorials(n,mod):
facs = [1 % mod]
for i in range(n):
facs += [facs[-1] * (i+1) % mod]
invs = [pow(facs[-1], -1, mod)]
for i in range(n):
invs += [invs[-1] * (n-i) % mod]
invs.reverse()
return facs, invs
def _ceil_pow2(n):
x = 0
while (1 << x) < n:
x += 1
return x
def _bsf(n):
x = 0
while n % 2 == 0:
x += 1
n //= 2
return x
class FenwickTree:
def __init__(self, n = 0):
self._n = n
self.data = [0] * n
def add(self, p, x):
assert 0 <= p < self._n
p += 1
while p <= self._n:
self.data[p - 1] += x
p += p & -p
def sum(self, left, right):
assert 0 <= left <= right <= self._n
return self._sum(right) - self._sum(left)
def _sum(self, r: int):
s = 0
while r > 0:
s += self.data[r - 1]
r -= r & -r
return s
class SegTree:
def __init__(self,
op: typing.Callable[[typing.Any, typing.Any], typing.Any],
e: typing.Any,
v: typing.Union[int, typing.List[typing.Any]]) -> None:
self._op = op
self._e = e
if isinstance(v, int):
v = [e] * v
self._n = len(v)
self._log = _ceil_pow2(self._n)
self._size = 1 << self._log
self._d = [e] * (2 * self._size)
for i in range(self._n):
self._d[self._size + i] = v[i]
for i in range(self._size - 1, 0, -1):
self._update(i)
def set(self, p: int, x: typing.Any) -> None:
assert 0 <= p < self._n
p += self._size
self._d[p] = x
for i in range(1, self._log + 1):
self._update(p >> i)
def get(self, p: int) -> typing.Any:
assert 0 <= p < self._n
return self._d[p + self._size]
def prod(self, left: int, right: int) -> typing.Any:
assert 0 <= left <= right <= self._n
sml = self._e
smr = self._e
left += self._size
right += self._size
while left < right:
if left & 1:
sml = self._op(sml, self._d[left])
left += 1
if right & 1:
right -= 1
smr = self._op(self._d[right], smr)
left >>= 1
right >>= 1
return self._op(sml, smr)
def all_prod(self) -> typing.Any:
return self._d[1]
def max_right(self, left: int,
f: typing.Callable[[typing.Any], bool]) -> int:
assert 0 <= left <= self._n
assert f(self._e)
if left == self._n:
return self._n
left += self._size
sm = self._e
first = True
while first or (left & -left) != left:
first = False
while left % 2 == 0:
left >>= 1
if not f(self._op(sm, self._d[left])):
while left < self._size:
left *= 2
if f(self._op(sm, self._d[left])):
sm = self._op(sm, self._d[left])
left += 1
return left - self._size
sm = self._op(sm, self._d[left])
left += 1
return self._n
def min_left(self, right: int,
f: typing.Callable[[typing.Any], bool]) -> int:
assert 0 <= right <= self._n
assert f(self._e)
if right == 0:
return 0
right += self._size
sm = self._e
first = True
while first or (right & -right) != right:
first = False
right -= 1
while right > 1 and right % 2:
right >>= 1
if not f(self._op(self._d[right], sm)):
while right < self._size:
right = 2 * right + 1
if f(self._op(self._d[right], sm)):
sm = self._op(self._d[right], sm)
right -= 1
return right + 1 - self._size
sm = self._op(self._d[right], sm)
return 0
def _update(self, k: int) -> None:
self._d[k] = self._op(self._d[2 * k], self._d[2 * k + 1])
class LazySegTree:
def __init__(
self,
op: typing.Callable[[typing.Any, typing.Any], typing.Any],
e: typing.Any,
mapping: typing.Callable[[typing.Any, typing.Any], typing.Any],
composition: typing.Callable[[typing.Any, typing.Any], typing.Any],
id_: typing.Any,
v: typing.Union[int, typing.List[typing.Any]]) -> None:
self._op = op
self._e = e
self._mapping = mapping
self._composition = composition
self._id = id_
if isinstance(v, int):
v = [e] * v
self._n = len(v)
self._log = _ceil_pow2(self._n)
self._size = 1 << self._log
self._d = [e] * (2 * self._size)
self._lz = [self._id] * self._size
for i in range(self._n):
self._d[self._size + i] = v[i]
for i in range(self._size - 1, 0, -1):
self._update(i)
def set(self, p: int, x: typing.Any) -> None:
assert 0 <= p < self._n
p += self._size
for i in range(self._log, 0, -1):
self._push(p >> i)
self._d[p] = x
for i in range(1, self._log + 1):
self._update(p >> i)
def get(self, p: int) -> typing.Any:
assert 0 <= p < self._n
p += self._size
for i in range(self._log, 0, -1):
self._push(p >> i)
return self._d[p]
def prod(self, left: int, right: int) -> typing.Any:
assert 0 <= left <= right <= self._n
if left == right:
return self._e
left += self._size
right += self._size
for i in range(self._log, 0, -1):
if ((left >> i) << i) != left:
self._push(left >> i)
if ((right >> i) << i) != right:
self._push(right >> i)
sml = self._e
smr = self._e
while left < right:
if left & 1:
sml = self._op(sml, self._d[left])
left += 1
if right & 1:
right -= 1
smr = self._op(self._d[right], smr)
left >>= 1
right >>= 1
return self._op(sml, smr)
def all_prod(self) -> typing.Any:
return self._d[1]
def apply(self, left: int, right: typing.Optional[int] = None,
f: typing.Optional[typing.Any] = None) -> None:
assert f is not None
if right is None:
p = left
assert 0 <= left < self._n
p += self._size
for i in range(self._log, 0, -1):
self._push(p >> i)
self._d[p] = self._mapping(f, self._d[p])
for i in range(1, self._log + 1):
self._update(p >> i)
else:
assert 0 <= left <= right <= self._n
if left == right:
return
left += self._size
right += self._size
for i in range(self._log, 0, -1):
if ((left >> i) << i) != left:
self._push(left >> i)
if ((right >> i) << i) != right:
self._push((right - 1) >> i)
l2 = left
r2 = right
while left < right:
if left & 1:
self._all_apply(left, f)
left += 1
if right & 1:
right -= 1
self._all_apply(right, f)
left >>= 1
right >>= 1
left = l2
right = r2
for i in range(1, self._log + 1):
if ((left >> i) << i) != left:
self._update(left >> i)
if ((right >> i) << i) != right:
self._update((right - 1) >> i)
def max_right(
self, left: int, g: typing.Callable[[typing.Any], bool]) -> int:
assert 0 <= left <= self._n
assert g(self._e)
if left == self._n:
return self._n
left += self._size
for i in range(self._log, 0, -1):
self._push(left >> i)
sm = self._e
first = True
while first or (left & -left) != left:
first = False
while left % 2 == 0:
left >>= 1
if not g(self._op(sm, self._d[left])):
while left < self._size:
self._push(left)
left *= 2
if g(self._op(sm, self._d[left])):
sm = self._op(sm, self._d[left])
left += 1
return left - self._size
sm = self._op(sm, self._d[left])
left += 1
return self._n
def min_left(self, right: int, g: typing.Any) -> int:
assert 0 <= right <= self._n
assert g(self._e)
if right == 0:
return 0
right += self._size
for i in range(self._log, 0, -1):
self._push((right - 1) >> i)
sm = self._e
first = True
while first or (right & -right) != right:
first = False
right -= 1
while right > 1 and right % 2:
right >>= 1
if not g(self._op(self._d[right], sm)):
while right < self._size:
self._push(right)
right = 2 * right + 1
if g(self._op(self._d[right], sm)):
sm = self._op(self._d[right], sm)
right -= 1
return right + 1 - self._size
sm = self._op(self._d[right], sm)
return 0
def _update(self, k: int) -> None:
self._d[k] = self._op(self._d[2 * k], self._d[2 * k + 1])
def _all_apply(self, k: int, f: typing.Any) -> None:
self._d[k] = self._mapping(f, self._d[k])
if k < self._size:
self._lz[k] = self._composition(f, self._lz[k])
def _push(self, k: int) -> None:
self._all_apply(2 * k, self._lz[k])
self._all_apply(2 * k + 1, self._lz[k])
self._lz[k] = self._id
# https://open.kattis.com/problems/mountaincraft
def solve2(case):
q,w=read()
l = [[*read()] for _ in range(q)]
s={0}
for i in range(q):
x,y=l[i]
l[i]=[max(x-y,0), min(x+y,w)]
s |= {*l[i]}
s=sorted(s)
# print(s)
d = {s[i]:i for i in range(len(s))}
val = [0] * len(s)
for i in range(len(s)-1):
val[i] = s[i+1] - s[i]
val[-1] = w - s[-1]
# print(s,val)
n = len(s)
sz = isqrt(n)
# print(n,sz,(n+sz-1)//sz)
b = [0] * ((n+sz-1)//sz)
# print(len(b), max(y//sz for _,y in l))
f = [Counter() for _ in range((n+sz-1)//sz)]
for i in range(len(s)):
f[i//sz][0] += val[i]
a = [0]*n
seen = set()
ans = w
for x,y in l:
x = d[x]
y = d[y]
# print(x,y)
if (x,y) in seen:
delta = -1
seen.remove((x,y))
else:
delta = 1
seen.add((x,y))
bx = x // sz
by = y // sz
# print(bx,by)
if bx == by:
ans -= f[bx][-b[bx]]
for i in range(x,y):
f[bx][a[i]] -= val[i]
a[i] += delta
f[bx][a[i]] += val[i]
ans += f[bx][-b[bx]]
else:
ans -= f[bx][-b[bx]]
for i in range(x,(x+sz)//sz*sz):
f[bx][a[i]] -= val[i]
a[i] += delta
f[bx][a[i]] += val[i]
ans += f[bx][-b[bx]]
ans -= f[by][-b[by]]
for i in range(y//sz*sz,y):
f[by][a[i]] -= val[i]
a[i] += delta
f[by][a[i]] += val[i]
ans += f[by][-b[by]]
for i in range(bx+1,by):
ans -= f[i][-b[i]]
b[i] += delta
ans += f[i][-b[i]]
# print(x,y)
# print(bx,by)
# print(delta)
# print(b)
# print(a)
# print(f)
# print(ans)
print((w-ans) * 2**.5)
# print()
def solve2(case):
adj = []
pre = []
res = []
order = []
order_rev = []
def ar_build(el):
for _ in range(n):
adj.append([])
pre.append([])
res.append(False)
for i,(x,y) in enumerate(el):
adj[x].append((y,i))
adj[y].append((x,i))
def ar_down(x, p=-1):
# val = False
# for y,ei in adj[x]:
# if y != p:
# val = val | ar_down(y,x)
# pre[x].append(val)
# return not val
for x,p in order:
val = False
for y,_ in adj[x]:
if y != p:
val = val | (not pre[y][-1] if pre[y] else True)
pre[x].append(val)
def ar_up(x,p=-1):
adj[x].reverse()
for y,ei in adj[x]:
if y == p: continue
if pre[x]: pre[x].pop()
res[y] = not ((res[x] or pre[x][-1]) if pre[x] else res[x])
res[x] = res[x] or not (pre[y][-1] if pre[y] else False)
ar_up(y,x)
res[x] = not res[x]
# for x,p in order_rev:
def calc(el):
ar_build(el)
order.append((0,-1))
order_rev.append((0,-1))
vis = [0] * n
vis_rev = [0] * n
ptr = 0
while ptr < len(order):
v,p = order[ptr]
vis[v] = 1
for vv,_ in adj[v]:
if not vis[vv]:
order.append((vv,v))
v,p = order_rev[ptr]
vis_rev[v] = 1
for vv,_ in reversed(adj[v]):
if not vis_rev[vv]:
order_rev.append((vv,v))
ptr += 1
order.reverse()
order_rev.reverse()
print(order)
ar_down(0)
ar_up(0)
n,q = read()
el = []
for _ in range(n-1):
x,y=read()
el.append((x-1,y-1))
calc(el)
for x in read():
print('Hermione' if res[x-1] else 'Ron')
def matmul(a,b,mod=0):
c = [[0]*len(b[0]) for i in range(len(a))]
for i in range(len(a)):
for k in range(len(b)):
for j in range(len(b[0])):
c[i][j] += a[i][k]*b[k][j]
if mod: c[i][j] %= mod
return c
def matpowmul(x,y,v,mod=0):
while y:
if y % 2: v = matmul(x,v,mod)
x = matmul(x,x,mod)
y //= 2
return v
def seg_sieve(n):
n = int(n)
S = 10**5
primes = []
nsqrt = isqrt(n)
is_prime = [1] * (nsqrt+2)
for i in range(2,nsqrt+1):
if is_prime[i]:
primes += [i]
for j in range(i*i,nsqrt+1,i):
is_prime[j] = 0
result = []
block = [0] * S
for k in range(n//S+1):
block[:] = [1]*S
start = k * S
for p in primes:
start_idx = (start + p - 1) // p
j = max(start_idx, p) * p - start
while j < S:
block[j] = 0
j += p
if k == 0:
block[0] = block[1] = 0
for i in range(S):
if start + i > n:
break
if block[i]:
result += [start+i]
return result
class HFIArray:
def __init__(S,n,mod=0):
S.n = n
a = 1 if n == 1 else int((2*n/log(n)) ** (2/3))
a = max(a, isqrt(n))
a = min(a, 10**8)
S.sieveLimit = a
S.mod = mod
S.sieveSum = [0] * (a+1)
S.val = [0] * (n//a + 1)
def __getitem__(S,v):
if v <= 0: return 0
if v <= S.sieveLimit: return S.sieveSum[v]
return S.val[S.n // v]
def __mul__(f,g):
n = f.n
a = f.sieveLimit
mod = f.mod
res = HFIArray(n,mod)
for x in range(1,a+1):
dfx = f.sieveSum[x] - f.sieveSum[x-1]
if dfx == 0: continue
for y in range(1,a//x+1):
res.sieveSum[x*y] += dfx * (g.sieveSum[y] - g.sieveSum[y-1])
if mod: res.sieveSum[x*y] %= mod
for i in range(1,a+1):
res.sieveSum[i] += res.sieveSum[i-1]
if mod: res.sieveSum[i] %= mod
for i in range(1,len(res.val)):
v = res.n // i
t = 0
s = isqrt(v)
for j in range(1,s+1):
t += (f[j] - f[j-1]) * g[v//j]
t += (g[j] - g[j-1]) * f[v//j]
if mod: t %= mod
t -= f[s] * g[s]
if mod: t %= mod
res.val[i] = t
return res
def __imul__(f,g):
a = f.sieveLimit
mod = f.mod
prod = [0] * (a+1)
for x in range(1,a+1):
dfx = f.sieveSum[x] - f.sieveSum[x-1]
if dfx == 0: continue
for y in range(1,a//x+1):
prod[x*y] += dfx * (g.sieveSum[y] - g.sieveSum[y-1])
if mod: prod[x*y] %= mod
for i in range(1,a+1):
prod[i] += prod[i-1]
if mod: prod[i] %= mod
for i in range(1,len(f.val)):
v = f.n // i
t = 0
s = isqrt(v)
for j in range(1,s+1):
t += (f[j] - f[j-1]) * g[v//j]
t += (g[j] - g[j-1]) * f[v//j]
if mod: t %= mod
t -= f[s] * g[s]
if mod: t %= mod
f.val[i] = t
f.sieveSum = prod
return f
def __pow__(f,y):
res = identityHFI(f.n,f.mod)
pw = HFIArray(f.n,f.mod)
pw.sieveSum = f.sieveSum[:]
pw.val = f.val[:]
while y:
if y & 1: res *= pw
pw *= pw
y >>= 1
return res
def identityHFI(n,mod=0):
res = HFIArray(n,mod)
for i in range(1,res.sieveLimit+1):
res.sieveSum[i] = 1
if mod: res.sieveSum[i] %= mod
for i in range(1,len(res.val)):
res.val[i] = 1
if mod: res.val[i] %= mod
return res
def unitHFI(n,mod=0):
res = HFIArray(n,mod)
for i in range(1,res.sieveLimit+1):
res.sieveSum[i] = i
if mod: res.sieveSum[i] %= mod
for i in range(1,len(res.val)):
res.val[i] = n // i
if mod: res.val[i] %= mod
return res
def powerfulExt(x, h):
nrt = isqrt(x)
res = [(1,1,0)]
ps = seg_sieve(nrt+1)
while res:
n,hn,i = res.pop()
if i >= len(ps) or (p := ps[i])**2 * n > x:
yield n,hn
continue
res.append((n,hn,i+1))
pp = p*p
e = 2
while pp*n <= x:
res.append((n*pp, hn*h(p,e), i+1))
if pp*n * p > x:
break
pp *= p
e += 1
def sumPowerfulPart(x,k,d):
@cache
def f(e):
return comb(e*k+d,d)
def h(p,e):
return _h(e) % mod
@cache
def _h(e):
return f(e) - sum(g(e-i) * _h(i) % mod for i in range(e)) % mod
v = comb(k+d,d)
print(f'{v = }')
@cache
def g(e):
return comb(e+v-1,e)
u = unitHFI(x,mod)
G = u ** v
t = 0
for n,hn in powerfulExt(x,h):
t += hn * G[x//n]
t %= mod
return t
def eea(a,b):
if not a: return b,0,1
g,x,y = eea(b%a,a)
return g, y - (b//a)*x, x
def crt(*c):
# print(c)
def f(c1,c2):
if c1 == (0,0) or c2 == (0,0): return (0,0)
m1,a1 = c1
m2,a2 = c2
g,x,_ = eea(m1,m2)
q,r = divmod(a2-a1,g)
# print(q,r)
if r: return 0,0
# print(m1,m2,g)
l = m1 // g * m2
return l, (a1 + q*x*m1) % l
return reduce(f,c)
mod=998244353
def solve(case):
# out = []
# for _ in range(int(input())):
# n,k,d = map(int,input().split())
# out.append(sumPowerfulPart(n,k,d))
# print(*out,sep='\n')
from decimal import getcontext
# getcontext().prec = 50
gamma = 0.57721566490153286060651209008240243
# gamma = dec(gamma)
n,=read()
def H(n):
if n < len(_H): return _H[n]
# v = dec(n).ln() + gamma + dec(1)/2/n - dec(1)/12/n/n #+ dec(1)/120/n**4
v = log(n) + gamma + 1/2/n - 1/12/n/n
# print(n,v,sum(1/k for k in range(1,n+1)))
# print(n,v)
return v
_H = [0]*(10**5+1)
for i in range(10**5):
_H[i+1] = _H[i] + 1/(i+1)
s = isqrt(n)
t = 0
for i in range(1,s+1):
t += 2*H(n//i) / i
t -= H(s)**2
print(t)
if __name__ == '__main__':
t = 1
# t = -1
# t, = read()
for i in range(1,t+1):
solve(i)