結果

問題 No.1936 Rational Approximation
コンテスト
ユーザー shobonvip
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

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