[NOIP2014]比例简化

题目描述

输入三个正整数 $A,B,L$ ，在 $1 \le A',B' \le L$ 、 $\gcd(A',B')=1$ 、 $A'/B' \ge A/B$ 的约束下，找使 $A'/B' - A/B$ 最小的 $(A',B')$ 。输出 $A'$ 、 $B'$ 。数据范围 $L \le 100$ 。

样例输入：1498 902 10，样例输出：5 3。

思路

枚举 $1 \le A',B' \le L$ 的每一对既约分数，用交叉相乘 $A' \cdot B \ge A \cdot B'$ 判断不小于原比例；误差比较也用交叉相乘，避免浮点；取差最小者，并列时按字典序取最小。

参考代码

Python 版：

python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-10-02 10:43
# update_at: 2026-10-02 10:43

import sys
from fractions import Fraction
from math import gcd


def best_ratio(a: int, b: int, limit: int) -> tuple[int, int]:
    """在分子、分母都不超过 limit 的既约分数里，找不小于 a/b 且与 a/b 差最小的那个。

    两个候选分数的差只取决于 x、y，用 Fraction 精确比较大小避免浮点误差；
    差相同时按 (x, y) 升序取最先枚举到的。
    """
    candidates = (
        (x, y)                                        # 合法候选：互质且 x/y >= a/b
        for x in range(1, limit + 1)
        for y in range(1, limit + 1)
        if gcd(x, y) == 1 and x * b >= a * y
    )
    return min(candidates, key=lambda p: (Fraction(p[0] * b - a * p[1], p[1] * b), p))


def solve() -> None:
    a, b, limit = map(int, sys.stdin.buffer.read().split())  # 题面的 A、B、L
    print(*best_ratio(a, b, limit))


if __name__ == "__main__":
    solve()

C++ 版（同一算法）：

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-06 15:14
 * update_at: 2026-10-06 15:14
 */

#include <iostream>
#include <algorithm>
#include <numeric>
using namespace std;

typedef long long ll;

ll A, B, L;            // 题面给定的 A、B、L
ll best_a, best_b;     // 当前最优的 A'、B'

// 判断候选 (x1,y1) 是否比 (x2,y2) 更优：误差更小，或误差相同则字典序更小
bool better(ll x1, ll y1, ll x2, ll y2) {
    // 误差分别为 (x1*B - A*y1)/(y1*B) 与 (x2*B - A*y2)/(y2*B)
    // 两正数分母相同因子 B 可约去，只需交叉相乘比较
    ll left  = (x1 * B - A * y1) * y2;
    ll right = (x2 * B - A * y2) * y1;
    if (left != right) return left < right;
    if (x1 != x2) return x1 < x2;
    return y1 < y2;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> A >> B >> L;

    bool first = true; // 是否已找到第一个合法候选
    for (ll a = 1; a <= L; ++a) {
        for (ll b = 1; b <= L; ++b) {
            if (gcd(a, b) != 1) continue;          // 必须互质
            if (a * B < A * b) continue;            // 必须不小于原比例 A/B
            if (first || better(a, b, best_a, best_b)) {
                best_a = a;
                best_b = b;
                first = false;
            }
        }
    }

    cout << best_a << ' ' << best_b << '\n';
    return 0;
}

目录

题目描述

思路

参考代码