結果

問題 No.1936 Rational Approximation
ユーザー shobonvipshobonvip
提出日時 2022-05-13 22:20:20
言語 PyPy3
(7.9.16)
結果
AC  
実行時間 83 ms / 2,000 ms
コード長 1,223 bytes
コンパイル時間 1,138 ms
実行使用メモリ 75,868 KB
最終ジャッジ日時 2023-02-21 15:09:14
合計ジャッジ時間 2,575 ms
ジャッジサーバーID
（参考情報） 		judge11 / judge13
このコードへのチャレンジ（β）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 82 ms
75,760 KB
testcase_01 AC 81 ms
75,536 KB
testcase_02 AC 82 ms
75,716 KB
testcase_03 AC 82 ms
75,504 KB
testcase_04 AC 83 ms
75,868 KB
testcase_05 AC 83 ms
75,752 KB
testcase_06 AC 83 ms
75,552 KB
testcase_07 AC 81 ms
75,760 KB
testcase_08 AC 83 ms
75,784 KB
testcase_09 AC 83 ms
75,432 KB
testcase_10 AC 82 ms
75,700 KB
testcase_11 AC 81 ms
75,648 KB
testcase_12 AC 82 ms
75,748 KB
testcase_13 AC 82 ms
75,592 KB
testcase_14 AC 83 ms
75,776 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

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)
0