专栏文章

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

tthis54
AT_abc408_g题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@mip5rtqo
此快照首次捕获于
2025/12/03 06:37
3 个月前
此快照最后确认于
2025/12/03 06:37
3 个月前
查看原文
递归解法
很明显，对于 a,b,c,da,b,c,d 当 ab<1\frac{a}{b}<1 且 cd>1\frac{c}{d}>1 时，一定能找到一个整数符合条件，此时 q=1q=1。
再者，当 ab≥1\frac{a}{b} \ge 1 且 cd>1\frac{c}{d}>1 时，因为不等是左右两边减去同一个数仍然满足，所以设 t=⌊a/b⌋t=\lfloor a / b \rfloor，a,b,c,da,b,c,d 转化为 a−bt,b,c−dt,da-bt,b,c-dt,d。
最后，当 ab<1\frac{a}{b}<1 且 cd≤1\frac{c}{d} \le 1 时，a,b,c,da,b,c,d 放缩为 d,c,b,ad,c,b,a 的结果 ×d÷c+1\times d \div c + 1（这一步的原因是我们尽量让这两个分数值回到第一种情况，很明显经过第二种情况时只有分母能拉开距离，最后推导出来就是这个结果）。
还有不要忘记开 __int128，不然你还想在场上调出高精度？
CPP
#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;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...