[C++知识库]分数拆分Uva10976C++(暴力枚举)

问题描述：
描述
现在输入一个正整数k,找到所有的正整数x>=y,使得
$$\frac{1}{k}=\frac{1}{x}+\frac{1}{y}$$

样式输入：
2
12
样式输出：
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

问题分析：
既然要找到所有的x,y枚举对象自然就是x,y，但是问题就在于枚举的问题如何下手？这里就需要一点数学素养在里面了，由
$$x>=y$$
得到
$$\frac{1}{x}<=\frac{1}{y}$$
因此
$$\frac{1}{k}?\frac{1}{y}<=\frac{1}{y}$$
所以
$$y<=2k$$
方法一：采用vector进行赋值，先枚举y的范围在[k+1,2*k]，通过k,y可以反写出x = ky/(y-k)，所以只要判断x是否为整数即可，如果是整数，就在两个容器里面分别增加该值。此运算速度也是非常快速。

#include <iostream>
#include <vector>

using namespace std;

int main(){
	int k;
	while(cin>>k){
		vector<int> X,Y;
		for(int y=k+1;y<=2*k;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);
			}	
		}
		cout<<X.size()<<endl;
		for(int i=0;i<X.size();i++){
			cout<<"1/"<<k<<"="<<"1/"<<X[i]<<"+1/"<<Y[i]<<endl;
		}
	}
	return 0;
}

下面附别人写的代码，通过自身演示时，当k很大的时候，该运算会变得很慢，不尽如人意。它的时间消耗在(xy)==(k(x+y))，这种比较上面了，运算时间也十分麻烦，故不推荐，当然也可以像我上面一样进行判断x是否为整数即可。

#include <iostream>

using namespace std;

int main()
{
	int k;
	while(cin>>k){
		int m=2*k;
		for(int y=k;y<=m;y++)
			for(int x=m;x<=m*m;x++)
			if((x*y)==(k*(x+y)))
				printf("1/%d=1/%d+1/%d\n",k,x,y);
	}
	return 0;
}