Uva 10976 暴力枚举来试试？

一、题意

输入正整数k，找到所有的正整数x>=y，使得 1/k = 1/x + 1/y。并打印出来。

二、解析

暴力枚举法。关键是缩小枚举范围。首先显然 k<x<=y，另一方面 y<=2k<=x。
因此可以发现y的范围是（k, 2k]，因此选择枚举y，时间复杂度仅为O(n)。

三、代码

#include <iostream>
#include <vector>
using namespace std;
struct xy {
    int x, y;
    xy(int x, int y) : x(x), y(y) {}
};
int k;
vector<xy> ans;

int main() {
    while(cin >> k) {
        ans.clear();
        for(int y = k + 1; y <= 2 * k; y ++) if(k * y % (y - k) == 0) {
            int x = k * y / (y - k);
            ans.push_back(xy(x, y));
        }
        cout << ans.size() << endl;
        for(auto & p : ans) cout << "1/" << k << " = 1/" << p.x << " + 1/" << p.y << endl;
    }
}

四、归纳

• 该枚举时就枚举，但是在枚举之前一定要分析时间复杂度。