結果
問題 | No.1936 Rational Approximation |
ユーザー |
![]() |
提出日時 | 2022-05-13 22:20:20 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 46 ms / 2,000 ms |
コード長 | 1,223 bytes |
コンパイル時間 | 162 ms |
コンパイル使用メモリ | 82,392 KB |
実行使用メモリ | 53,564 KB |
最終ジャッジ日時 | 2024-07-22 02:19:37 |
合計ジャッジ時間 | 1,518 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 14 |
ソースコード
p,q = map(int,input().split()) def xgcd(a,b): prevx, nextx = 1, 0 prevy, nexty = 0, 1 while b: quotient = a//b nextx, prevx = prevx - quotient * nextx, nextx nexty, prevy = prevy - quotient * nexty, nexty a, b = b, a % b return prevx, prevy # P/Q < Rp/Rq # P Rq < Rp Q # Rp Q - P Rq = できれば 1 # Lp/Lq < P/Q # P Lq - Q Lp = 1 # P Lq + Q (-Lp) # Rqをでかく! # Q Rp + P (-Rq) = 1 ans = 0 s,t = xgcd(q,p) if t<=-q: # t>-q にする # s-=p, t+=q # s-k*p, t+k*q (>-q) # t+k*q>-q # k*q>-q-t # k>(-q-t)/q # k>=(-t-1)//q k=(-t)//q s -= k*p t += k*q else: # t>-q の最大値 # s+=p, t-=q # s+k*p, t-k*q (>-q) # t-k*q>-q # k*q<t+q # k<(t+q)/q # k<=(t+q-1)//q k=(t+q-1)//q s += k*p t -= k*q #print(s,t) ans += s ans += -t #print(p/q) #print(s/(-t)) # Q (-Lp) + P Lq = 1 s,t = xgcd(q,p) if t>=q: #print("HERE") # t<q にする # s+=p, t-=q # s+k*p, t-k*q (<q) # t-q < k*q # (t-q)/q < k # (t-q+q-1)/q # (t-q+q-1)//q <= k # (t-1)//q <= k k=t//q s += k*p t -= k*q else: # t<q の最大値 # s-=p, t+=q # s-k*p, t+k*q (<q) # t+k*q<q # k*q<q-t # k<(q-t)/q # k<=(q-t-1)//q k=(q-t-1)//q s -= k*p t += k*q ans -= s ans += t #print(s,t) #print(s/(-t)) print(ans)