按刘汝佳书上解法做的（注意递归什么时候结束）
#include<stdio.h> #include<string.h> int maxd; int ans[100]; int temp[100]; int smallestdeno(int a,int b) { int res = b/a; return res*a >= b?res:res+1; } int gcd(int a,int b) { return b==0? a:gcd(b,a%b); } int max(int a,int b) { return a>b ? a: b; } bool better(int cur) { for(int i=cur; i >= 0; --i) { if(ans[i]==-1 || temp[i]<ans[i]) return true; } return false; } bool dfs(int cur,int a,int b,int from) { if(cur == maxd) { if(b % a) return false; temp[cur] = b/a; if(better(cur)) { memcpy(ans,temp,sizeof(temp)); } return true; } int start = max(from,smallestdeno(a,b)); bool ok = false; for(int i = start;; ++i) { if((maxd+1-cur)*b <= a*i ) break; temp[cur] = i; int aa = a*i-b; int bb = b*i; int g = gcd(bb,aa); bool res = dfs(cur+1, aa/g, bb/g, i+1); if(res) ok = 1; } return ok; } int main() { int a,b; while(scanf("%d%d", &a, &b)==2) { for(maxd = 1;;maxd++) { memset(ans,-1,sizeof(ans)); memset(temp,-1,sizeof(temp)); if(dfs(0,a,b,0)) break; } int i=0; while(ans[i]!=-1) { printf("%d ",ans[i]); i++; } putchar(10); } }
