Official

G - A/B < p/q < C/D Editorial by en_translator

First, we claim that if we take the minimum \(q\), the corresponding value \(p\) is uniquely determined if \(q\neq 1\).

Proof

For simplicity, we consider the case where $\displaystyle \frac{A}{B} < \frac CD \le 1$.

For the minimum $q>1$ satisfying the condition, if $\displaystyle \frac pq$ and $\displaystyle \frac{p+1}q$ both satisfy the condition, then $\displaystyle \frac pq < \frac p{q-1} <\frac{p+1}q$, so letting $q = q-1$ also satisfy the condition, which is contradiction.

Thus, instead of directly finding \(q\), we will find the pair \((p,q)\) with minimum \(q\). For convenience, if \(q=1\), we will minimize \(p\). Let \(\displaystyle f\left( \frac AB,\frac CD\right) = (p,q)\) denote the answer to this problem.

Here, \(\displaystyle f\left( \frac AB,\frac CD\right)\) can be found recursively by the following algorithm.

  • Let \(\displaystyle n=\left\lfloor \frac AB\right\rfloor\). For \(\displaystyle (p,q) = f\left(\frac AB - n, \frac CD - n\right) \) we have \(\displaystyle f\left( \frac AB,\frac CD\right)=(p+nq,q)\), so it is reduced to the case with \(\displaystyle \frac AB<1\).
  • If \(\displaystyle \frac CD > 1\), then \(q=1\) satisfies the condition, so \(\displaystyle f\left( \frac AB,\frac CD\right)=(1,1)\).
  • If \(\displaystyle \frac CD\le 1\), then for \(\displaystyle (p,q)= f\left( \frac DC,\frac BA\right)\) we have \(\displaystyle f\left( \frac AB,\frac CD\right)=(q,p)\), so we can reduce it to a smaller case.

Considering the continued fraction expansion of a rational number, this procedure terminates after \(O(\log \max\lbrace A,B,C,D\rbrace)\) steps.

The problem can be solved by appropriately implementing them. The time complexity is \(O(\log \max\lbrace A,B,C,D\rbrace)\) per test case.

Sample code (Python 3)

import sys
input = sys.stdin.readline

def solve(a, b, c, d):
    n = a // b
    a -= n * b
    c -= n * d
    if c > d:
        return n + 1, 1
    p, q = solve(d, c, b, a)
    return p * n + q, p

for _ in range(int(input())):
    a, b, c, d = map(int, input().split())
    p, q = solve(a, b, c, d)
    print(q)

Sample code (C++)

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
pair<ll, ll> solve(ll a, ll b, ll c, ll d) {
	ll n = a / b;
	a -= n * b, c -= n * d;
	if (c > d)
		return {n + 1, 1};
	auto [p, q] = solve(d, c, b, a);
	return {p * n + q, p};
}
int main() {
	cin.tie(nullptr);
	ios::sync_with_stdio(false);
	int t;
	cin >> t;
	while (t--) {
		ll a, b, c, d;
		cin >> a >> b >> c >> d;
		auto [p, q] = solve(a, b, c, d);
		cout << q << '\n';
	}
}

posted:
last update: