洛谷:P2118
OJ: P4943
A
、反对人数 B
和最大比例上限 L
。min_diff_num = -1
记录最小差值。这里用 -1
初始化是为了方便后续比较是否有找到更小的比例差。min_n
和 min_d
分别记录最终化简后的分子和分母。d
:
d
从 1 到上限 L
。d
,计算使得 n / d >= A / B
的最小 n
,公式为:cpp复制代码long long n_min = (A * d + B - 1) / B;
这个公式是为了向上取整,确保 n / d
大于等于 A / B
。n
:
n_min
开始尝试寻找符合条件的 n
,且保证 gcd(n, d) == 1
。n
,就计算当前比例的差值:cpp复制代码long long diff_num = n * B - A * d;
n
,所以可以直接跳出 n
的循环,减少不必要的计算。-1
初始化差值方便后续的条件判断,避免复杂的比较逻辑。n
和 d
,即化简后的比例。代码实现:
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 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 | /**************************************************************** * Description: 2014普及组 比例简化 * Author: Alex Li * Date: 2024-10-09 22:45:16 * LastEditTime: 2024-10-09 22:45:29 ****************************************************************/ #include <iostream> #include <algorithm> #define LL long long using namespace std; // 计算最大公约数(GCD)的函数 int gcd(int a, int b) { return b == 0 ? a : gcd(b, a % b); } int main() { freopen("ratio.in","r",stdin); freopen("ratio.out","w",stdout); // 输入支持人数 A,反对人数 B,以及比例上限 L LL A, B, L; cin >> A >> B >> L; // 初始化用于存储最小差值的变量 LL min_diff_num = -1; // 用于记录最小差值的分子部分 LL min_n = 0, min_d = 1; // 分别记录化简后的分子和分母 // 枚举可能的分母 d,范围从 1 到 L for (LL d = 1; d <= L; ++d) { // 计算使得 n/d >= A/B 的最小 n 值,这个写法是为了向上取整,确保 n / d 大于等于 A / B。 LL n_min = (A * d + B - 1) / B; if (n_min > L) continue; // 如果 n_min 超过上限 L,则跳过当前分母 d // 尝试从 n_min 开始寻找最小的 n,使得 gcd(n, d) == 1 for (LL n = n_min; n <= L; ++n) { if (gcd(n, d) == 1) { // 确保 n 和 d 互质 // 计算差值的分子部分:n * B - A * d LL diff_num = n * B - A * d; // 如果找到的差值更小,则更新最优结果 if (min_diff_num == -1 || diff_num * min_d < min_diff_num * d) { min_diff_num = diff_num; // 更新最小差值 min_n = n; // 更新最优分子 min_d = d; // 更新最优分母 } break; // 因为 n_min 已是最小 n,因此可以直接跳出循环 } } } // 输出化简后的比例结果 cout << min_n << " " << min_d << endl; return 0; } |