AcWing 458. 比例简化
原题链接
简单
作者:
王小强
,
2021-02-11 10:28:56
,
所有人可见
,
阅读 424
寒假作业打卡
#include <iostream>
#include <algorithm>
using namespace std;
int a, b, l, _a, _b;
int main(void) {
cin >> a >> b >> l; // a == 分子, b == 分母,l == limit 上限
// Delta是第四个希腊字母的读音,其大写为Δ,小写为δ。在数学或者物理学中大写的Δ用来表示增量符号。
double delta = 1e9;
for (int i = 1; i <= l; ++i) // 穷举所有不超过上限的分子分母
for (int j = 1; j <= l; ++j)
if (__gcd(i, j) == 1) { // 如果分子分母互质的化 (两个整数的最大公约数是1)
double x = static_cast<double>(i) / j; // 估计比值
double y = static_cast<double>(a) / b; // 实际比值
if (x >= y && x - y < delta) {
_a = i;
_b = j;
delta = x - y;
}
}
printf("%d %d\n", _a, _b);
}