[NOIP 2014 普及组] 比例简化

GitHub跳转原题关系图返回列表

按分母 1..L 枚举，为每个分母找到不小于 A/B 的最小互质分子，再在这些候选里取最小分数。

OJ: luogu

题目 ID: P2118

难度:普及-

标签:数论枚举最大公约数

日期: 2026-06-18 22:20

目录

  1. 题意
  2. 思路
  3. 代码
  4. 复杂度
  5. 总结

题意

给出一个原始比例 A:B，以及上限 L。
要找一组 A', B'，满足：

  • A', B' <= L
  • gcd(A', B') = 1
  • A'/B' >= A/B

并且在所有满足条件的分数中，A'/B' 要尽量小。

思路

先看一个可以直接验证想法的朴素解：

把所有 1 <= A', B' <= L 的组合都枚举一遍，只保留：

  • 互质的
  • 不小于 A/B 的

然后在里面取最小分数。

cpp
// brute.cpp：小数据暴力解，用来帮助理解题意并辅助对拍。
#include <bits/stdc++.h>
using namespace std;

using ll = long long;

ll A, B, L;

ll gcd_ll(ll x, ll y) {
    while (y != 0) {
        ll t = x % y;
        x = y;
        y = t;
    }
    return x;
}

void solve() {
    ll ans_a = 0, ans_b = 1;

    for (ll a = 1; a <= L; a++) {
        for (ll b = 1; b <= L; b++) {
            if (gcd_ll(a, b) != 1) {
                continue;
            }
            if (a * B < A * b) {
                continue;
            }
            if (ans_a == 0 || a * ans_b < ans_a * b) {
                ans_a = a;
                ans_b = b;
            }
        }
    }

    cout << ans_a << ' ' << ans_b << '\n';
}

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

    cin >> A >> B >> L;
    solve();

    return 0;
}

这个做法已经能过，但它做了很多没必要的枚举。

关键观察是：如果分母固定成某个 b，那么最优分子一定是“第一个刚好够大”的那个。

也就是说，先算：

a = ceil(A*b / B)

这时 a/b 已经是这个分母下最靠近 A/B 的合法起点。
如果它和 b 不互质，就把 a 继续往上加，直到找到第一个互质分子。

下面这张表可以帮助理解样例 1498/902：

分母 b 最小满足 a/b >= 1498/902 的 a 第一个互质候选 候选分数
1 2 2 2/1
2 4 5 5/2
3 5 5 5/3
4 7 7 7/4

表格第三列表示在固定分母下真正需要比较的那个候选。
从这些候选里再挑最小分数，就能得到最终答案 5/3。

所以正式做法是：

  1. 枚举 b = 1..L
  2. 计算 a = ceil(A*b/B)
  3. 若 gcd(a,b) != 1，继续增大 a
  4. 若最终 a <= L，就得到这个分母下的最优候选
  5. 在所有候选中取最小分数

代码

cpp
#include <bits/stdc++.h>
using namespace std;

using ll = long long;

ll A, B, L;

ll gcd_ll(ll x, ll y) {
    while (y != 0) {
        ll t = x % y;
        x = y;
        y = t;
    }
    return x;
}

void solve() {
    ll ans_a = 0, ans_b = 1;

    for (ll b = 1; b <= L; b++) {
        ll a = (A * b + B - 1) / B;  // ceil(A*b / B)

        while (a <= L && gcd_ll(a, b) != 1) {
            a++;
        }
        if (a > L) {
            continue;
        }

        if (ans_a == 0 || a * ans_b < ans_a * b) {
            ans_a = a;
            ans_b = b;
        }
    }

    cout << ans_a << ' ' << ans_b << '\n';
}

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

    cin >> A >> B >> L;
    solve();

    return 0;
}

复杂度

由于 L <= 100，即使用整数枚举也很轻松。
正式做法的时间复杂度不超过 O(L2)O(L^2)，空间复杂度是 O(1)O(1)。

总结

这题的重点不是“枚举所有分子分母”，而是看出：

  • 固定分母后，只需要找第一个合法互质分子。

这样就能把问题缩成“每个分母只保留一个候选”，实现会清楚很多。