? ? ? ?由于題目意思指的是將分數拆分成不同的單位分數之和，所以就不用考慮將2/3拆成1/3+1/3這種情況了；又由于好的拆分要求項數即len
要少，最小的項要大，故可以采用迭代加深搜索，按項數不斷增大的順序進行搜索；對每一種len，要用一個數組將其的所有情況記錄下來，
但這樣太耗空間了，因此將情況保存在ans數組里，然后對ans不斷進行更新。具體實現時，要設兩個標志flag,flag1,flag用來判斷是不是
第一次搜索len長的拆分，flag1用來判斷是否需要對ans進行更新。還有就是每次搜索的起點要弄好，后面的要比前面的大，要將a/b-1/z作
為新的搜索分數，其中z為當前搜到的符合要求的項。然后就可以比較方便地實現了。
1 #include<stdio.h> 2 3 #include<string.h> 4 5 typedef long long ll; 6 ll a,b,pre[1005],ans[1005]; 7 int flag; 8 ll max(ll x,ll y) 9 { 10 if(x>y)return x; 11 return y; 12 } 13 ll gcd(ll small,ll big) 14 { 15 ll temp; 16 if(big<small) 17 { 18 temp=big;big=small;small=temp; 19 } 20 if(big%small==0)return small; 21 return gcd(big%small,small); 22 } 23 void ids(ll x,ll y,int len,int cur) 24 { 25 ll i,j,k; 26 if(cur==len) 27 { 28 if(x==1) 29 { 30 pre[len]=y; 31 if(!flag) 32 { 33 for(i=1;i<=len;i++) 34 ans[i]=pre[i]; 35 } 36 else 37 { 38 int temp,flag1=0; 39 for(temp=len;temp>0;temp--) 40 { 41 if(pre[temp]>ans[temp])break; 42 if(pre[temp]<ans[temp])flag1=1; 43 if(flag1)break; 44 } 45 if(flag1) 46 { 47 for(i=1;i<=len;i++) 48 ans[i]=pre[i]; 49 } 50 } 51 flag=1; 52 } 53 return ; 54 } 55 j=y/x; 56 if(j<2)j=2; 57 j=max(pre[cur-1]+1,j); 58 while(x*j-y<=0)j++; 59 while(1) 60 { 61 ll z=x*j-y; 62 ll m=y*j; 63 k=gcd(z,m); 64 z/=k;m/=k; 65 if(len-cur<(z*j)/m)return ; 66 if(z*j>=(len-cur)*m)return ; 67 pre[cur]=j; 68 ids(z,m,len,cur+1); 69 j++; 70 } 71 } 72 int main() 73 { 74 int i,j,T; 75 ll k; 76 scanf("%d",&T); 77 while (T--) 78 { 79 scanf("%lld%lld",&a,&b); 80 k=gcd(a,b); 81 a/=k;b/=k; 82 pre[0]=1; 83 for(i=1;i<=1000;i++) 84 { 85 flag=0; 86 ids(a,b,i,1); 87 if(flag)break; 88 } 89 for(j=1;j<=i;j++) 90 printf("%lld ",ans[j]); 91 printf("\n"); 92 } 93 return 0; 94 }
?
))
】)
