题解：AT_abc408_g [ABC408G] A/B < p/q < C/D

this54 · 2025-06-01 16:47:58 · 题解

递归解法

很明显，对于 a,b,c,d 当 \frac{a}{b}<1 且 \frac{c}{d}>1 时，一定能找到一个整数符合条件，此时 q=1。

再者，当 \frac{a}{b} \ge 1 且 \frac{c}{d}>1 时，因为不等是左右两边减去同一个数仍然满足，所以设 t=\lfloor a / b \rfloor，a,b,c,d 转化为 a-bt,b,c-dt,d。

最后，当 \frac{a}{b}<1 且 \frac{c}{d} \le 1 时，a,b,c,d 放缩为 d,c,b,a 的结果 \times d \div c + 1（这一步的原因是我们尽量让这两个分数值回到第一种情况，很明显经过第二种情况时只有分母能拉开距离，最后推导出来就是这个结果）。

还有不要忘记开 __int128，不然你还想在场上调出高精度？

#include <cstdio>
using namespace std;
#define int __int128
inline void read(int& n) {
    int x = 0, f = 1;
    char ch = getchar();
    while (ch < '0' || ch>'9') {
        if (ch == '-') f = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9') {
        x = (x << 1) + (x << 3) + (ch ^ 48);
        ch = getchar();
    }
    n = x * f;
}
inline void print(int n) {
    if (n < 0) {
        putchar('-');
        n *= -1;
    }
    if (n > 9) print(n / 10);
    putchar(n % 10 + '0');
}//切记__int128没有cin cout
int f(int a, int b, int c, int d)
{
    if (a < b)
    {
        if (c > d) return 1;
        else return f(d, c, b, a) * d / c + 1;
    }
    else
    {
        int k = a / b;
        return f(a - k * b, b, c - k * d, d);
    }
}
signed main()
{
    int n;
    read(n);
    int a, b, c, d, p;
    while (n--)
    {
        read(a);read(b);read(c);read(d);
        print(find(a, b, c, d));puts("");
    }
    return 0;
}