比例简化¹

题目信息

见链接

解题思路

这里的$L\le 100$，非常良心。

那我们就…

枚举！

一言不合就枚举

咳咳，不皮了。

整理一下思路，差不多是这样：

枚举A’和B’。

判断A’和B’是否互质（gcd(A’,B’)=1）

判断A’/B’是否大于A/B

判断A’/B’是否为最小。

整理一下，就差不多是这样了。

#include <cstdio> using namespace std; int a, b, a_, b_, L; int gcd(int, int); bool judge(int, int); int main() { scanf("%d %d %d", &a, &b, &L); a_ = L; b_ = 1; //----暴力枚举----// for (int i = 1; i <= L; i++) for (int j = 1; j <= L; j++) if (judge(i, j)) { a_ = i; b_ = j; } printf("%d %d", a_, b_); return 0; } //判断函数 bool judge(int i, int j) { if (gcd(i, j) == 1 && i * b >= j * a && i * b_ < j * a_) return true; return false; } //求x和y的最小公倍数 int gcd(int x, int y) { return (y == 0) ? x : gcd(y, x % y); }

---

2013年NOIP普及组第2题 ↩︎