結果
| 問題 | No.2266 Fractions (hard) |
| ユーザー |
 chineristAC
|
| 提出日時 | 2023-04-08 00:58:52 |
| 言語 | PyPy3 (7.3.15) |
| 結果 |
AC
|
| 実行時間 | 5,460 ms / 6,000 ms |
| コード長 | 6,690 bytes |
| コンパイル時間 | 454 ms |
| コンパイル使用メモリ | 82,600 KB |
| 実行使用メモリ | 79,300 KB |
| 最終ジャッジ日時 | 2024-04-14 12:00:44 |
| 合計ジャッジ時間 | 41,906 ms |
|
ジャッジサーバーID （参考情報） |
judge1 / judge4 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 135 ms
78,776 KB |
| testcase_01 | AC | 2,015 ms
78,888 KB |
| testcase_02 | AC | 243 ms
78,352 KB |
| testcase_03 | AC | 66 ms
70,404 KB |
| testcase_04 | AC | 76 ms
74,936 KB |
| testcase_05 | AC | 114 ms
78,444 KB |
| testcase_06 | AC | 307 ms
79,300 KB |
| testcase_07 | AC | 176 ms
78,308 KB |
| testcase_08 | AC | 141 ms
79,016 KB |
| testcase_09 | AC | 97 ms
77,968 KB |
| testcase_10 | AC | 105 ms
78,144 KB |
| testcase_11 | AC | 71 ms
70,892 KB |
| testcase_12 | AC | 137 ms
78,400 KB |
| testcase_13 | AC | 2,529 ms
78,784 KB |
| testcase_14 | AC | 161 ms
78,092 KB |
| testcase_15 | AC | 177 ms
78,120 KB |
| testcase_16 | AC | 2,601 ms
79,108 KB |
| testcase_17 | AC | 1,635 ms
78,864 KB |
| testcase_18 | AC | 3,278 ms
78,908 KB |
| testcase_19 | AC | 2,095 ms
78,916 KB |
| testcase_20 | AC | 159 ms
78,076 KB |
| testcase_21 | AC | 2,706 ms
78,744 KB |
| testcase_22 | AC | 1,548 ms
79,236 KB |
| testcase_23 | AC | 193 ms
78,060 KB |
| testcase_24 | AC | 192 ms
77,888 KB |
| testcase_25 | AC | 3,911 ms
79,020 KB |
| testcase_26 | AC | 195 ms
78,148 KB |
| testcase_27 | AC | 1,985 ms
78,764 KB |
| testcase_28 | AC | 195 ms
77,972 KB |
| testcase_29 | AC | 194 ms
78,160 KB |
| testcase_30 | AC | 194 ms
78,152 KB |
| testcase_31 | AC | 194 ms
77,848 KB |
| testcase_32 | AC | 1,817 ms
78,772 KB |
| testcase_33 | AC | 63 ms
69,792 KB |
| testcase_34 | AC | 391 ms
78,556 KB |
| testcase_35 | AC | 391 ms
78,564 KB |
| testcase_36 | AC | 5,460 ms
79,276 KB |
| testcase_37 | AC | 3,855 ms
78,652 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)