【每日一题34】AcWing 458. 比例简化

发表于 更新于 分类于 Valine：
本文字数： 97 阅读时长 ≈ 1 分钟

Day34 AcWing 458. 比例简化

思路

  1. 枚举
  2. 题解

由于 $L$ 在100以内，枚举 $A’$ ,$B’$ 的所有组合，然后进行判断

  • $\frac {A’} {B’}$是否大于等于$\frac A B$，并且最小

代码

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
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

int gcd(int a, int b)
{
    return b ? gcd(b, a % b) : a;
}

int main()
{
    int A, B, L;
    cin >> A >> B >> L;

    int a, b;
    double delta = 1e9;
    for (int i = 1; i <= L; i ++ )
        for (int j = 1; j <= L; j ++ )
            if (gcd(i, j) == 1)
            {
                double x = i * 1.0 / j;
                double X = A * 1.0 / B;

                if (x >= X && x - X < delta)
                {
                    delta = x - X;
                    a = i, b = j;
                }
            }

    cout << a << ' ' << b << endl;

    return 0;
}