結果
問題 | No.2266 Fractions (hard) |
ユーザー | とりゐ |
提出日時 | 2023-04-07 22:38:26 |
言語 | PyPy3 (7.3.15) |
結果 |
TLE
(最新)
AC
(最初)
|
実行時間 | - |
コード長 | 1,963 bytes |
コンパイル時間 | 487 ms |
コンパイル使用メモリ | 82,796 KB |
実行使用メモリ | 86,512 KB |
最終ジャッジ日時 | 2024-04-14 11:55:43 |
合計ジャッジ時間 | 43,544 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge1 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 129 ms
76,712 KB |
testcase_01 | AC | 2,868 ms
79,272 KB |
testcase_02 | AC | 646 ms
79,144 KB |
testcase_03 | AC | 47 ms
62,224 KB |
testcase_04 | AC | 70 ms
68,212 KB |
testcase_05 | AC | 91 ms
76,356 KB |
testcase_06 | AC | 218 ms
77,604 KB |
testcase_07 | AC | 131 ms
76,164 KB |
testcase_08 | AC | 85 ms
76,440 KB |
testcase_09 | AC | 75 ms
76,360 KB |
testcase_10 | AC | 75 ms
75,992 KB |
testcase_11 | AC | 53 ms
64,216 KB |
testcase_12 | AC | 99 ms
76,164 KB |
testcase_13 | AC | 1,996 ms
78,804 KB |
testcase_14 | AC | 237 ms
77,328 KB |
testcase_15 | AC | 259 ms
77,612 KB |
testcase_16 | AC | 4,169 ms
78,936 KB |
testcase_17 | AC | 2,705 ms
78,912 KB |
testcase_18 | TLE | - |
testcase_19 | AC | 5,874 ms
78,992 KB |
testcase_20 | AC | 220 ms
77,112 KB |
testcase_21 | TLE | - |
testcase_22 | AC | 1,118 ms
78,864 KB |
testcase_23 | AC | 284 ms
78,096 KB |
testcase_24 | AC | 286 ms
77,720 KB |
testcase_25 | TLE | - |
testcase_26 | -- | - |
testcase_27 | -- | - |
testcase_28 | -- | - |
testcase_29 | -- | - |
testcase_30 | -- | - |
testcase_31 | -- | - |
testcase_32 | -- | - |
testcase_33 | -- | - |
testcase_34 | -- | - |
testcase_35 | -- | - |
testcase_36 | -- | - |
testcase_37 | -- | - |
ソースコード
def quotient_range(n): ret=[] i=1 while i<=n: q=n//i j=n//q+1 ret.append((i,j)) i=j return ret 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 def mertens_table(n): if n==0: return [[0],[0]] b=10**4 small=[1]*(n//b+1) large=[1]*(b+1) small[0]=0 large[0]=0 prime=[1]*(n//b+1) for p in range(2,n//b+1): if not prime[p]: continue for j in range(p,n//b+1,p): if j>p: prime[j]=0 if j%(p*p)==0: small[j]=0 else: small[j]*=-1 for i in range(1,n//b): small[i+1]+=small[i] for i in range(b,0,-1): l=2 while l<=n//i: q=n//(i*l) r=n//(i*q)+1 if i*l<=b: large[i]-=large[i*l]*(r-l) else: large[i]-=small[n//(i*l)]*(r-l) l=r return small,large def range_g(L,R,P,Q): return floor_sum(R,Q,P,0)-floor_sum(L,Q,P,0) def count(n,P,Q): res=0 for L,R in QR: x=n//L if x<len(small): res+=small[x]*range_g(L,R,P,Q) else: res+=large[n//x]*range_g(L,R,P,Q) return res for _ in range(1): n,k=map(int,input().split()) small,large=mertens_table(n) QR=quotient_range(n) c=count(n,n*n-1,n*n) if k==c+1: print('1/1') continue if k<=c: rev=False elif k<=2*c+1: rev=True k=2*c+2-k else: print(-1) continue ng,ok=-1,n*n while ok-ng>1: mid=(ok+ng)>>1 if count(n,mid,n*n)>=k: ok=mid else: ng=mid ng2,ok2=0,n*n while ok2-ng2>1: mid=(ok2+ng2)>>1 cnt1=floor_sum(mid,n*n,ok-1,ok-1) cnt2=floor_sum(mid,n*n,ok,ok) if cnt1!=cnt2: ok2=mid else: ng2=mid den=ok2 num=ok*den//(n*n) if rev: den,num=num,den print(str(num)+'/'+str(den))