UVa10976 Fractions Again?!（分数拆分）
1、题目
2、题意
输入正整数 k k k，找到所有正整数 x ≥ y x \ge y x≥y，使得 1 k = 1 x + 1 y \frac{1}{k} = \frac{1}{x} + \frac{1}{y} k1=x1+y1。
3、分析
既然要求找出所有的 x , y x,y x,y，枚举对象自然是 x , y x,y x,y了。可问题在于，枚举的范围如何？从 1 / 12 = 1 / 156 + 1 / 13 1/12 = 1/156 + 1/13 1/12=1/156+1/13 可以看出， x x x 可以比 y y y 大很多。难道要无休止枚举下去？当然不是。由于 x ≤ y x \le y x≤y，有 1 x ≤ 1 y \frac{1}{x} \le \frac{1}{y} x1≤y1，因此 1 k − 1 y ≤ 1 y \frac{1}{k} - \frac{1}{y} \le \frac{1}{y} k1−y1≤y1，即 y ≤ 2 k y \le 2k y≤2k。这样，只需要在 2 k 2k 2k 范围之内枚举 y y y，然后根据 y y y 尝试计算出 x x x 即可。
4、代码实现
#include<cstdio>
#include<vector>
using namespace std;
int main() {
int k;
while(scanf("%d", &k) == 1 && k) {
vector<int> X, Y;
for(int y = k+1; y <= k*2; y++) {
// 1/k = 1/x + 1/y => x = ky/(y-k)
if(k*y%(y-k) == 0) {
X.push_back(k*y/(y-k));
Y.push_back(y);
}
}
printf("%d\n", X.size());
for(int i = 0; i < X.size(); i++)
printf("1/%d = 1/%d + 1/%d\n", k, X[i], Y[i]);
}
return 0;
}