【练习-7】(Uva 10976)Fractions Again?!(分数拆分）

翻译：

输入正整数k,找到所有的正整数x≥y，使得
$$\frac{1}{k}=\frac{1}{x}+\frac{1}{y}$$
这个题也是很有意思，搞一些提前的运算：
既然要求找出所有的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+1,2k]范围内枚举y，然后根据y尝试计算出x即可。
（内容来自紫书）
这也太好了！

AC代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e5+5;
const ll mod = 1e9+7;
int main()
{
    
	int n;
	while(cin>>n && n)
	{
    
		int cnt = 0;
		for(int i=n+1;i<=2*n;i++)
			if((i*n)%(i-n)==0)
				cnt++;
		cout<<cnt<<endl;
		for(int i=n+1;i<=2*n;i++)
			if((i*n)%(i-n)==0)
				printf("1/%d = 1/%d + 1/%d\n",n,(i*n)/(i-n),i);
	}
}

直接写两遍一边算cnt一边输出是因为我太懒了。。。可能有简单的方法？？额应该差不多吧。
中间的判断思路是这样的：1/k = 1/x +1/y，也就是说 1/k - 1/y = 1/x就是满足条件的。
等式左边化简一下就是 y/ky - k/ky ==》 (y-k)/yk 也就是说只要这个式子能化简成 1/？就是满足条件的。
也就是 1/(yk/(y-k))的分母是个整数。也就是yk%(y-k) ==0
因此得到了代码中的那个算式。

总结：

这样算式的题，要用未知数来推出几个新的算式简化题目。
主要就是推式子，推不出来就完犊子了。。。