UVA 10976 分数拆分（数论+枚举）

Discription

给定一个k，构造一个等式 1/k = 1/x + 1/y ，其中x>=y。

Input

输入不超过100行（0 < k ≤ 10000）

Output

输出x y的数目和x y的值。

Sample Input

2
12

Sample Output

2
1/2 = 1/6 + 1/3
1/2 = 1/4 + 1/4
8
1/12 = 1/156 + 1/13
1/12 = 1/84 + 1/14
1/12 = 1/60 + 1/15
1/12 = 1/48 + 1/16
1/12 = 1/36 + 1/18
1/12 = 1/30 + 1/20
1/12 = 1/28 + 1/21
1/12 = 1/24 + 1/24

Solution

既然要求找出所有的x、y,枚举对象自然就是x、y了。可问题在于,枚举的范围如何?从1/12=1/156+1/13可以看出,x可以比y大很多。由于x≥y,有1/x <= 1/y，因此1/k - 1/y <= 1/y，所以y >= 2k，只需要在k~2k之间枚举y，由y计算x即可。

Code

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <cstring>

using namespace std;

int main()
{
// freopen("in.txt", "r", stdin);
int k;
while (~scanf("%d", &k))
    {
vector<int> X, Y;
for (int y = k + 1; y <= 2 * k; y++)
        {
if (0 == k * y % (y - k) && y != k)
            {
int x = k * y / (y - k);
                X.push_back(x);
                Y.push_back(y);
            }
        }
printf("%lu\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;
}