NOIP2014普及組T2（比例簡化）題解

文章目錄

• 題目資訊
• 解題思路：模拟
• 代碼實作

題目資訊

題目傳送門

解題思路：模拟

• 對于一個比例x : y：

  若(x : y) < (a : b)，則x加1，分母相同的情況下最小幅度的增加分數大小；

  若(x : y) > (a : b)，則y加1，分字相同的情況下最小幅度的減小分數大小。

• 注意：

  有的時候浮點數精确度不夠（double雙精度是四舍五入至小數點後6位），那麼就需要交叉相乘比較，即

  (x : y) < (a : b)等價于xb < ya。

• 加速（常數級優化）

  如果x和y不互質，就肯定枚舉過了，不用重複看。

代碼實作

#include <bits/stdc++.h>
using namespace std;
int main() {
    int a, b, l;
    cin >> a >> b >> l;
    int x = l, y = 1;
    for (int i = 1; i <= l; ++i) {
        for (int j = 1; j <= l; ++j) {
            if (__gcd(i, j) == 1 && i * b >= j * a && i * y < j * x) {
                x = i;
                y = j;
            }
        }
    }
    cout << x << ' ' << y << '\n';
    return 0;
}