結果
| 問題 | No.2262 Fractions |
| ユーザー |
 chineristAC
|
| 提出日時 | 2023-04-07 22:46:53 |
| 言語 | PyPy3 (7.3.15) |
| 結果 |
TLE
|
| 実行時間 | - |
| コード長 | 5,489 bytes |
| コンパイル時間 | 418 ms |
| コンパイル使用メモリ | 82,476 KB |
| 実行使用メモリ | 92,156 KB |
| 最終ジャッジ日時 | 2024-04-10 17:41:43 |
| 合計ジャッジ時間 | 4,222 ms |
|
ジャッジサーバーID （参考情報） |
judge4 / judge2 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 171 ms
92,156 KB |
| testcase_01 | TLE | - |
| testcase_02 | -- | - |
| testcase_03 | -- | - |
| testcase_04 | -- | - |
| testcase_05 | -- | - |
| testcase_06 | -- | - |
| testcase_07 | -- | - |
| testcase_08 | -- | - |
| testcase_09 | -- | - |
| testcase_10 | -- | - |
| testcase_11 | -- | - |
| testcase_12 | -- | - |
| testcase_13 | -- | - |
| testcase_14 | -- | - |
| testcase_15 | -- | - |
| testcase_16 | -- | - |
| testcase_17 | -- | - |
| testcase_18 | -- | - |
| testcase_19 | -- | - |
| testcase_20 | -- | - |
| testcase_21 | -- | - |
| testcase_22 | -- | - |
| testcase_23 | -- | - |
| testcase_24 | -- | - |
| testcase_25 | -- | - |
| testcase_26 | -- | - |
| testcase_27 | -- | - |
| testcase_28 | -- | - |
| testcase_29 | -- | - |
| testcase_30 | -- | - |
| testcase_31 | -- | - |
| testcase_32 | -- | - |
| testcase_33 | -- | - |
| testcase_34 | -- | - |
| testcase_35 | -- | - |
| testcase_36 | -- | - |
| testcase_37 | -- | - |
| testcase_38 | -- | - |
| testcase_39 | -- | - |
| testcase_40 | -- | - |
| testcase_41 | -- | - |
| testcase_42 | -- | - |
| testcase_43 | -- | - |
| testcase_44 | -- | - |
| testcase_45 | -- | - |
ソースコード
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: int, m: int, a: int, b: int) -> int:
ans = 0
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
ans += floor_sum(y_max, a, m, (a - x_max % a) % a)
return ans
M = 3*10**5 + 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]
def solve(N,K):
lower = (0,1)
upper = (1,0)
calc = 0
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 = 0
ng = t
while ng-ok>1:
mid = (ok+ng)//2
if (q*mid+q)//p <= t:
ok = mid
else:
ng = mid
tmp = (t+1) * ng - floor_sum(ng,p,q,q)
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 = 0
ng = t
while ng-ok>1:
mid = (ok+ng)//2
if (q*mid+q)//p <= t:
ok = mid
else:
ng = mid
tmp = (t+1) * ng - floor_sum(ng,p,q,q)
res += tmp * (mebius_cum[k_r] - mebius_cum[k_l-1])
#for q in range(1,N//(B+1)+1):
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(int(input())):
N,K = mi()
solve(N,K)