51Nod 1187. 寻找分数(类欧几里得)

日付: 10月 20, 2018

[寻找分数问题 - 51Nod](https://www.51nod.com/onlineJudge/questionCode.html#!problemId=1187)

## Problem
找出最小的$q$，使$\frac{a}{b} < \frac{p}{q} < \frac{c}{d}, \quad a, b, c, d, p, q \in \mathbb{N}$

数据范围：样例数10000

## Solution
可以用**类欧几里得**。首先可以发现求最小的$p$和$q$是等价的，求出一个就可以算出另一个。分情况讨论：
1. 如果$\frac{a}{b}$是假分数，两边同时减去$\lfloor\frac{a}{b}\rfloor$后对$q$没有影响，而$\frac{a}{b}$不再是假分数
2. 如果$\frac{a}{b}$是真分数

2.1 如果$\frac{d}{c}$是假分数，可以取倒得到$\frac{d}{c} < \frac{q}{p} < \frac{b}{a}$转化为情况1，然后求出最小的$p$，再算出$q$

2.2 如果$\frac{d}{c}$是真分数，说明$\frac{c}{d} > 1$，直接令$p = q = 1$

## Code
```c++
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
using PLL = pair<LL, LL>;

LL solve(LL a, LL b, LL c, LL d) {
    return a >= b ? solve(a % b, b, c - a / b * d, d) :
           c > d ? 1 : solve(d, c, b, a) * d / c + 1;
}

int main() {
    int t;
    scanf("%d", &t);
    while (t--) {
        LL a, b, c, d;
        scanf("%lld%lld%lld%lld", &a, &b, &c, &d);
        LL q = solve(a, b, c, d), p = a * q / b + 1;
        printf("%lld/%lld\n", p, q);
    }
    return 0;
}
```

KONGROOの基地

このブログを検索

51Nod 1187. 寻找分数(类欧几里得)

コメント

コメントを投稿