Description
在古埃及，人们使用单位分数的和(形如1/a的, a是自然数)表示一切有理数。
如：2/3=1/2+1/6,但不允许2/3=1/3+1/3,因为加数中有相同的。
对于一个分数a/b,表示方法有很多种，但是哪种最好呢？
首先，加数少的比加数多的好，其次，加数个数相同的，最小的分数越大越好。
如：
19/45=1/3 + 1/12 + 1/180
19/45=1/3 + 1/15 + 1/45
19/45=1/3 + 1/18 + 1/30,
19/45=1/4 + 1/6 + 1/180
19/45=1/5 + 1/6 + 1/18.
最好的是最后一种，因为1/18比1/180,1/45,1/30,1/180都大。
给出a,b(0〈a〈b〈1000),编程计算最好的表达方式。
如：2/3=1/2+1/6,但不允许2/3=1/3+1/3,因为加数中有相同的。
对于一个分数a/b,表示方法有很多种，但是哪种最好呢？
首先，加数少的比加数多的好，其次，加数个数相同的，最小的分数越大越好。
如：
19/45=1/3 + 1/12 + 1/180
19/45=1/3 + 1/15 + 1/45
19/45=1/3 + 1/18 + 1/30,
19/45=1/4 + 1/6 + 1/180
19/45=1/5 + 1/6 + 1/18.
最好的是最后一种，因为1/18比1/180,1/45,1/30,1/180都大。
给出a,b(0〈a〈b〈1000),编程计算最好的表达方式。
Input
一行包含a,b(0〈a〈b〈1000)。
Output
每组测试数据若干个数，自小到大排列，依次是单位分数的分母。
不同的OJ好像数据不太一样...因为最优解的标准不同 要改一下better函数（这样可以得到正解 但不一定AC...T_T）
#include<iostream>
#include<cstring>
#include<cstdio>
#define maxl 100000
#define LL long long
using namespace std;
LL maxd,ans[maxl],v[maxl];
LL gcd(LL a,LL b){
?a:gcd(b,a%b);
}
LL get(LL a,LL b){
LL c=b/a;
if(b%a) c++;
return c;
}
/*bool better(){
for(int i=maxd;i>=0;i--){
if(ans[i]==-1||v[i]<ans[i]) return true;
if(v[i]>ans[i]) return false;
}
return false;
}*/
bool better() {
;i--)if(v[i]!=ans[i]){
||v[i]<ans[i];
}
return false;
//return v[maxd]<ans[maxd]||ans[maxd]==-1;
}
bool dfs(LL d,LL from,LL a,LL b){
if(d==maxd){
if(b%a) return false;
v[d]=b/a;
if(v[d]<from) return false;
if(better()){
;i<=maxd;i++) ans[i]=v[i];
}
return true;
}
LL k=max(from,get(a,b));
bool flag=false;
for(LL i=k;;i++){
)*b<i*a) break;
v[d]=i;
LL aa=a*i-b;
LL bb=b*i;
LL g=gcd(aa,bb);
,i+,aa/g,bb/g)) flag=true;
}
return flag;
}
void print(){
printf(]);
;i<=maxd;i++) printf(" %lld",ans[i]);
}
int main()
{
LL a,b;
scanf("%lld%lld",&a,&b);
memset(ans,-,sizeof(ans));
;;maxd++){
,get(a,b),a,b)) break;
}
print();
;
}