まず、条件を満たす最小の \(q\) を取った時に、 \(q\neq 1\) なら対応する \(p\) は一つに定まります。

よって、 \(q\) を求めるのではなく最小の \(q\) を持つ \((p,q)\) の組を求めることを考えます。ただし、便宜上 \(q=1\) の時は \(p\) が最小になるように取ることにします。この問題を \(\displaystyle f\left( \frac AB,\frac CD\right) = (p,q)\) と表記します。

ここで、 \(\displaystyle f\left( \frac AB,\frac CD\right)\) は以下のアルゴリズムで再帰的に求めることができます。

• \(\displaystyle n=\left\lfloor \frac AB\right\rfloor\) とする。 \(\displaystyle (p,q) = f\left(\frac AB - n, \frac CD - n\right) \) に対し \(\displaystyle f\left( \frac AB,\frac CD\right)=(p+nq,q)\) となるので、これにより \(\displaystyle \frac AB<1\) の場合に帰着させることができる。
• もし \(\displaystyle \frac CD > 1\) なら \(q=1\) が条件を満たすので \(\displaystyle f\left( \frac AB,\frac CD\right)=(1,1)\) となる。
• \(\displaystyle \frac CD\le 1\) の場合、 \(\displaystyle (p,q)= f\left( \frac DC,\frac BA\right)\) として \(\displaystyle f\left( \frac AB,\frac CD\right)=(q,p)\) が成り立つことを使い小さいケースに帰着させる。

有理数の連分数展開を考えることでこれらのステップは \(O(\log \max\lbrace A,B,C,D\rbrace)\) ステップで終了することが分かります。

以上を適切に実装することでこの問題を解くことができます。計算量は各テストケース毎に \(O(\log \max\lbrace A,B,C,D\rbrace)\) です。

実装例(Python3)

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)

実装例(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';
	}
}