結果
| 問題 | No.2266 Fractions (hard) |
| ユーザー |
 chineristAC
|
| 提出日時 | 2023-04-08 00:58:52 |
| 言語 | PyPy3 (7.3.15) |
| 結果 |
AC
|
| 実行時間 | 5,437 ms / 6,000 ms |
| コード長 | 6,690 bytes |
| コンパイル時間 | 271 ms |
| コンパイル使用メモリ | 82,608 KB |
| 実行使用メモリ | 79,532 KB |
| 最終ジャッジ日時 | 2024-10-03 09:15:25 |
| 合計ジャッジ時間 | 41,307 ms |
|
ジャッジサーバーID （参考情報） |
judge5 / judge2 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 130 ms
78,312 KB |
| testcase_01 | AC | 1,983 ms
78,892 KB |
| testcase_02 | AC | 238 ms
78,108 KB |
| testcase_03 | AC | 65 ms
69,248 KB |
| testcase_04 | AC | 80 ms
72,832 KB |
| testcase_05 | AC | 119 ms
78,512 KB |
| testcase_06 | AC | 314 ms
79,276 KB |
| testcase_07 | AC | 170 ms
78,336 KB |
| testcase_08 | AC | 138 ms
78,884 KB |
| testcase_09 | AC | 94 ms
78,144 KB |
| testcase_10 | AC | 103 ms
78,356 KB |
| testcase_11 | AC | 68 ms
70,656 KB |
| testcase_12 | AC | 131 ms
78,436 KB |
| testcase_13 | AC | 2,496 ms
78,908 KB |
| testcase_14 | AC | 163 ms
77,968 KB |
| testcase_15 | AC | 175 ms
78,080 KB |
| testcase_16 | AC | 2,592 ms
78,652 KB |
| testcase_17 | AC | 1,615 ms
78,888 KB |
| testcase_18 | AC | 3,232 ms
78,776 KB |
| testcase_19 | AC | 2,043 ms
78,920 KB |
| testcase_20 | AC | 153 ms
78,080 KB |
| testcase_21 | AC | 2,690 ms
78,784 KB |
| testcase_22 | AC | 1,589 ms
79,316 KB |
| testcase_23 | AC | 197 ms
78,336 KB |
| testcase_24 | AC | 195 ms
77,952 KB |
| testcase_25 | AC | 3,879 ms
79,012 KB |
| testcase_26 | AC | 198 ms
78,116 KB |
| testcase_27 | AC | 1,984 ms
78,892 KB |
| testcase_28 | AC | 193 ms
77,824 KB |
| testcase_29 | AC | 194 ms
78,188 KB |
| testcase_30 | AC | 192 ms
77,952 KB |
| testcase_31 | AC | 197 ms
77,992 KB |
| testcase_32 | AC | 1,827 ms
78,768 KB |
| testcase_33 | AC | 62 ms
68,224 KB |
| testcase_34 | AC | 393 ms
78,848 KB |
| testcase_35 | AC | 392 ms
78,720 KB |
| testcase_36 | AC | 5,437 ms
79,532 KB |
| testcase_37 | AC | 3,821 ms
78,648 KB |
ソースコード
import sys,random,bisect
from collections import deque,defaultdict
from heapq import heapify,heappop,heappush
from itertools import permutations
from math import gcd,log
input = lambda :sys.stdin.readline().rstrip()
mi = lambda :map(int,input().split())
li = lambda :list(mi())
from collections import deque
class Dinic:
def __init__(self, N):
self.N = N
self.G = [[] for i in range(N)]
def add_edge(self, fr, to, cap):
forward = [to, cap, None]
forward[2] = backward = [fr, 0, forward]
self.G[fr].append(forward)
self.G[to].append(backward)
def add_multi_edge(self, v1, v2, cap1, cap2):
edge1 = [v2, cap1, None]
edge1[2] = edge2 = [v1, cap2, edge1]
self.G[v1].append(edge1)
self.G[v2].append(edge2)
def bfs(self, s, t):
self.level = level = [None]*self.N
deq = deque([s])
level[s] = 0
G = self.G
while deq:
v = deq.popleft()
lv = level[v] + 1
for w, cap, _ in G[v]:
if cap and level[w] is None:
level[w] = lv
deq.append(w)
return level[t] is not None
def dfs(self, v, t, f):
if v == t:
return f
level = self.level
for e in self.it[v]:
w, cap, rev = e
if cap and level[v] < level[w]:
d = self.dfs(w, t, min(f, cap))
if d:
e[1] -= d
rev[1] += d
return d
return 0
def flow(self, s, t):
flow = 0
INF = 10**9 + 7
G = self.G
while self.bfs(s, t):
*self.it, = map(iter, self.G)
f = INF
while f:
f = self.dfs(s, t, INF)
flow += f
return flow
def floor_sum(n,m,a,b):
ans=0
while True:
if a>=m:
ans+=(n-1)*n*(a//m)//2
a%=m
if b>=m:
ans+=n*(b//m)
b%=m
y_max=(a*n+b)//m
x_max=(y_max*m-b)
if y_max==0:
return ans
ans+=(n-(x_max+a-1)//a)*y_max
n,m,a,b=y_max,a,m,(a-x_max%a)%a
M = 10**4 + 1
mebius = [1] * (M+1)
prime = [True] * (M+1)
for p in range(2,M+1):
if not prime[p]:
continue
for n in range(p,M+1,p):
if n%(p*p) == 0:
mebius[n] = 0
mebius[n] *= -1
prime[n] = False
mebius_cum = [mebius[n] for n in range(M+1)]
mebius[0] = 0
for n in range(1,M):
mebius_cum[n+1] += mebius_cum[n]
for N in range(1,100):
tmp = 0
for n in range(1,N+1):
tmp += mebius_cum[N//n]
assert tmp == 1
def solve(N,K):
lower = (0,1)
upper = (1,0)
calc = 0
B = int(N**.5)
big_mertens = [0] * (B+10)
for n in range(1,B+10)[::-1]:
"""
Mertens(N/n)を計算
sum M(N/ni) for i in 1...N/n = 1
を利用
"""
tmp = 0
T = N//n
"""
sum M(T/i) for i in 2...N/n
を計算
"""
TB = int(T**.5)
for i in range(2,TB+1):
if M < T//i :
tmp += big_mertens[n*i]
else:
tmp += mebius_cum[T//i]
for Q in range(1,T//(TB+1)+1):
"""
q <= N/(n*i) < q+1
N//(q+1)*i+1 <= i <= N//n*q
"""
L = max(N//((Q+1)*n)+1,2)
R = min(N//(Q*n),N//n)
if L<=R:
tmp += (R-L+1) * mebius_cum[Q]
big_mertens[n] = 1 - tmp
def cond(p,q):
nonlocal calc
calc += 1
#assert p <= N and q <= N
"""
・qx<=py
・1 <= x,y <= N
・gcd(x,y)=1
をみたすx,yを数える
gcd(x,y)がkの倍数とすると
sum((N//k)-(qi)//p for i in range(1,(N//k)+1))
-> floor_sum
+メビウス変換
"""
res = 0
B = int(N**.5)
for k in range(1,B+1):
t = N//k
tmp = 0
ok = max(-1,(p*t+1-q)//q)
ng = min(t,((t+1)*p+1-q)//q+1)
while ng-ok>1:
mid = (ok+ng)//2
if (q*mid+q-1)//p <= t:
ok = mid
else:
ng = mid
tmp = t * ng - floor_sum(ng,p,q,q-1)
res += tmp * mebius[k]
for t in range(1,N//(B+1)+1):
k_l = N//(t+1)+1
k_r = N//t
tmp = 0
ok = max(-1,(p*t+1-q)//q)
ng = min(t,((t+1)*p+1-q)//q+1)
while ng-ok>1:
mid = (ok+ng)//2
if (q*mid+q-1)//p <= t:
ok = mid
else:
ng = mid
tmp = t * ng - floor_sum(ng,p,q,q-1)
c = 0
if k_r <= M:
c += mebius_cum[k_r]
else:
c += big_mertens[t]
if k_l-1 <= M:
c -= mebius_cum[k_l-1]
else:
c -= big_mertens[t+1]
res += tmp * c
return res
if cond(N,1) < K:
print(-1)
return
while True:
a,b = lower
c,d = upper
p,q = (a+c,b+d)
check = cond(p,q)
if check < K:
"""
右に潜る
"""
ok = 1
if d!=0:
ng = min((N-b)//d,(N-a)//c) + 1
else:
ng = (N-a)//c + 1
while ng-ok>1:
mid = (ok+ng)//2
p,q = a+c*mid,b+d*mid
xxx = cond(p,q)
if xxx < K:
ok = mid
elif K < xxx:
ng = mid
else:
p,q = a+c*mid,b+d*mid
print("{}/{}".format(p,q))
return
lower = (a+c*ok,b+d*ok)
elif K < check:
"""
左に潜る
"""
ok = 1
if a!=0:
ng = min((N-d)//b,(N-c)//a) + 1
else:
ng = (N-d)//b + 1
while ng-ok>1:
mid = (ok+ng)//2
p,q = a*mid+c,b*mid+d
if cond(p,q) > K:
ok = mid
else:
ng = mid
upper = (a*ok+c,b*ok+d)
else:
print("{}/{}".format(p,q))
return
for _ in range(1):
N,K = mi()
solve(N,K)