GESP 1-4级 -- GESP 5-8级 -- CSP-J/S --

A32869. $最接近的分数分母不超过 N 且小于 A/B 的最大最简分数是多少？输入三个正整数 N，A，B，相邻两个数之间用单个空格隔开。1 <= A < B <N <= 1000。输出两个正整数，分别是所求分数的分子和分母，中间用单个空格隔开。样例输入100 7 13样例输出50 93$

填空题中等

知识点

枚举最大公约数分数比较

题目描述

最接近的分数 分母不超过 N 且 小于 A/B 的最大最简分数是多少？ 输入 三个正整数 N，A，B，相邻两个数之间用单个空格隔开。1 <= A < B <N <= 1000。 输出 两个正整数，分别是所求分数的分子和分母，中间用单个空格隔开。 样例输入 100 7 13 样例输出 50 93

参考答案

#include <iostream>
using namespace std;

int main()
{
    int n, a, b, p, q, x, y;

    scanf("%d%d%d", &n, &a, &b);

    // 分子x从1-n，分母y从n-1；结果p/q，开始时1/n（最小值）
    p = 1, q = n;
    for(x=1; x<=n; x++)
        for(y=n; y>=1; y--)
            if(b * x < a * y && x * q > p * y)
                p = x, q = y;

    printf("%d %d\n", p, q);

    return 0;
}

上一题下一题