亲爱的题解被简书吃掉了。。。下面只贴代码。。。
#include <iostream>
#include <algorithm>
#include <cstdlib>
#include <cstdio>
#include <cstring>
using namespace std;
int a,b,maxd,flag;
int ans[15],v[15];
int gcd(int aa,int bb){
return bb == 0 ? aa : gcd(bb,aa%bb);
}
void dfs(int d,int aa,int bb){
if(d == maxd){
if(bb%aa==0 && bb/aa > v[d-1]){
v[d] = bb/aa;
for(int i = 1; i <=maxd; i++) cout<<v[i]<<" ";
cout<<endl;
if(!flag || v[d] < ans[d])
for(int i = 1; i <=maxd; i++) ans[i] = v[i];
flag = 1;
return;
}
return;
}
int s = bb/aa+1;
s = max(s,v[d-1]+1);
int t = max((maxd-d+1)*bb/aa,s);
//printf("maxd %d d %d s %d t %d aa %d bb %d\n",maxd,d,s,t,aa,bb);
for(int i = s;i <= t;i++){
v[d] = i;
printf("maxd %d d %d i %d\n",maxd,d,i);
int aa2 = aa*i-bb;
int bb2 = bb*i;
int g = gcd(aa2,bb2);
dfs(d+1,aa2/g,bb2/g);
}
}
int main(){
while(scanf("%d %d",&a,&b) == 2){
flag = 0;
for(maxd = 2;maxd <= 10;maxd++){
memset(v, -1, sizeof(v));
dfs(1,a,b);
if(flag){
printf("%d/%d=",a,b);
for(int i=1;i<maxd;i++)
printf("1/%d+",ans[i]);
printf("1/%d\n",ans[maxd]);
break;
}
}
if(!flag)
printf("No solutuon\n");
}
}
。。。我知道写得很垃圾。。。因为今天真的很困。。。而且亲爱的轮子哥又在跟我逼逼本科直接找工作不要刷那么多题。。。多做工程。。。问题系。。。我现在不仅做不动而且没人一起做阿。。。。
