异想天开

What's the true meaning of light, Could you tell me why

分数拆分

日期:2015-05-07 12:27:27
  
最后更新日期:2015-05-07 12:27:27
南洋OJ
http://acm.nyist.net/JudgeOnline/problem.php?pid=66
描述
现在输入一个正整数k,找到所有的正整数x>=y,使得1/k=1/x+1/y.

输入
第一行输入一个整数n,代表有n组测试数据。
接下来n行每行输入一个正整数k
输出
按顺序输出对应每行的k找到所有满足条件1/k=1/x+1/y的组合
样例输入
2
2
12
解释:
x,y都为正整数,1/x+1/y=1/k,变形为k(x+y)=xy,继续变形,ky=x*(y-k),可以看出y要大于k,那么x=ky/(y-k),上下都为y的一次,可以提出一个常数,那么y为k+1时,x最大,x最小为y的最小值k+1。程序如下:
[code lang="cpp"]
#include<stdio.h>
int sovle(){
int n,k,xMax,yMin,x,y;
scanf("%d",&n);
while(n--){
scanf("%d",&k);
xMax=(k+1)*k;
yMin=k+1;
for (x=xMax;x>=yMin;x--){
for (y=yMin;y<=x;y++){
if (k*(x+y)==x*y){
printf("1/%d=1/%d+1/%d\n",k,x,y);
}
}
}
printf("\n");
}
return 0;
}

int main()
{
sovle();
return 0;
}
[/code]
PS:
新后台上线测试下书写功能。