CFR 806 A. Success Rate ( Math, Extended GCD )

Problem - A - Codeforces

題意：
你現在寫了 y 個題目，答對了 x 個。你想知道你最少要再寫幾題才能有答對比率 p / q。若無解輸出 -1。

制約：
The first line contains a single integer t (1 ≤ t ≤ 1000) — the number of test cases.
Each of the next t lines contains four integers x, y, p and q (0 ≤ x ≤ y ≤ 1e9; 0 ≤ p ≤ q ≤ 1e9; y > 0; q > 0).
It is guaranteed that p / q is an irreducible fraction.

解法：
假設你至少要再答 a 個題目，其中 b 題要答對才能達到目標，那麼條件可以這樣表示：
( x + b ) / ( y + a ) = p / q
整理一下得：
p * y - q * x = q * b - p * a
因為左式是定值，令它為 r，接著求使得 q * x + p * y = gcd( q, p ) 的一組 x, y。
如果 r 不是 gcd( q, p ) 的倍數一定無解。
這組 x, y 可以對應到一組滿足條件的 b = r / gcd( p, q ) * y, a = r / gcd( p, q ) * ( -x )。
因為題目要求的是滿足 0 ≤ b ≤ a 且最小的 a，所以加加減減再搞一下就可以。
一直溢位所以用 python。
然而這題大家都是用智慧的二分搜秒掉。

時間 / 空間複雜度：
O( lg y )

def gcd( a, b ):
  return a if b == 0 else gcd( b, a % b )

def ext_gcd( a, b ):
  if b == 0:
    return [ 1, 0 ]
  xx, yy = ext_gcd( b, a % b )
  return [ yy, xx - a // b * yy ]

T = int( input() )
for ti in range( T ):
  x, y, p, q = map( int, input().split() )
  r = p * y - q * x
  b, a = ext_gcd( q, p )
  a *= -1
  a *= r // gcd( p, q )
  b *= r // gcd( p, q )
  p, q = q, p
  if a >= 0 and b >= 0:
    k = min( a // p, a // p if q == 0 else b // q )
    a -= k * p
    b -= k * q
  if a < 0:
    k = ( -a + p - 1 ) // p
    a += k * p
    b += k * q
  if b < 0 and q:
    k = ( -b + q - 1 ) // q
    a += k * p
    b += k * q
  if a < b and p > q:
    k = ( b - a + p - q - 1 ) // ( p - q )
    a += k * p
    b += k * q
  if not ( 0 <= b <= a ):
    print( -1 )
  else:
    print( a )