結果

問題 No.1936 Rational Approximation
ユーザー shobonvipshobonvip
提出日時 2022-05-13 22:20:20
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 79 ms / 2,000 ms
コード長 1,223 bytes
コンパイル時間 707 ms
コンパイル使用メモリ 87,128 KB
実行使用メモリ 71,228 KB
最終ジャッジ日時 2023-09-29 07:44:48
合計ジャッジ時間 2,742 ms
ジャッジサーバーID
（参考情報） 		judge11 / judge12
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 79 ms
71,164 KB
testcase_01 AC 77 ms
71,228 KB
testcase_02 AC 77 ms
71,096 KB
testcase_03 AC 76 ms
71,124 KB
testcase_04 AC 74 ms
71,224 KB
testcase_05 AC 75 ms
71,092 KB
testcase_06 AC 76 ms
71,056 KB
testcase_07 AC 76 ms
70,952 KB
testcase_08 AC 77 ms
71,144 KB
testcase_09 AC 79 ms
71,012 KB
testcase_10 AC 77 ms
71,136 KB
testcase_11 AC 75 ms
71,056 KB
testcase_12 AC 73 ms
71,084 KB
testcase_13 AC 77 ms
70,728 KB
testcase_14 AC 76 ms
71,056 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