/** 题目：埃及分数问题 链接：lrj算法竞赛入门经典P206 题意：在古埃及，人们使用单位分数的和(即 1/a, a是自然数)表示一切有理数。例如，2/3 = 1/2+1/6; 但不允许:2/3 = 1/3 + 1/3; 因为在加数中不允许有相同的。 对一个分数a/b， 表示方法有很多种，其中加数少的比加数多的好，如果加数个数相同，则最小的分数越大越好。 eg: 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最大。 思路：迭代加深搜索！ 控制迭代的层数。从一个加数，两个加数，。。。，maxd个加数搜索。 假设：当前maxed层。以递增顺序枚举分母，假设当前枚举到第i个加数为1/e; 那么前i个分数之和sa/sb + (maxd-i)*1/e（因为后面的分母肯定更大，那么值肯定更小，估算最大可能的值） < a/b（要分解的分数）; 说明在已经确定前i个数的情况下，maxd层无法满足。可以不用继续枚举下去。从而剪枝。 如果已经获得了前i个分数之和sa/sb， 那么接下来枚举的1/e应该满足1/e+sa/sb<=a/b; 即：1/e<=a/b-sa/sb; 找出 最小的满足条件的e。从它开始枚举之后递增的分母。从而剪枝。 */ #include <iostream> #include <cstdio> #include <vector> #include <cstring> #include <cmath> #include <algorithm> using namespace std; typedef long long LL; const int mod=1e9+7; const int maxn=1e2+5; const double eps = 1e-12; LL ans[1004]; LL v[1004]; LL a, b; LL f(LL a,LL b) { for(LL i = b/a; ; i++){///1/i <= a/b; => b<=a*i; => b/a<=i if(a*i>=b) return i; } return -1; } LL gcd(LL a,LL b) { return b==0?a:gcd(b,a%b); } bool better(int pos) { for(int i = pos; i >= 1; i--){ if(v[i]!=ans[i]){ return ans[i]==-1||v[i]<ans[i]; } } return false; } bool dfs(int pos,int maxd,int from,LL a,LL b) { if(pos==maxd){ if(b%a!=0) return false; ///无法满足分解； v[pos] = b/a; if(better(pos)){ memcpy(ans+1,v+1,sizeof(LL)*(maxd+1)); } return true; } from = max(from*1LL,f(a,b)); int ok = 0; for(int i = from; ; i++){ if(b*(maxd-pos+1)<=a*i)///1/i + (maxd-pos)/i <= a/b; ///这里必须等于，因为如果不等于，会出现相同的加数。其中一个这里得来， ///还有一个在终止条件 v[pos] = b/a;那里得来。 { break; } v[pos] = i; LL aa = a*i-b; LL bb = b*i; LL g = gcd(aa,bb); if(dfs(pos+1,maxd,i+1,aa/g,bb/g)){ ok = true; } } return ok; } int main() { while(scanf("%lld%lld",&a,&b)==2)///a<b { int ok = 0; LL ta = a, tb = b; LL g = gcd(a,b); a = a/g; b = b/g; memset(ans, -1, sizeof ans); memset(v, -1, sizeof v); int maxd; for(maxd = 1; ; maxd++){ if(dfs(1,maxd,f(a,b),a,b)) {///第1个加数开始，maxd层，f(a,b)表示第一个最小的e，a,b表示要分解的分数。 ok = 1; break; } } //cout<<"maxd = "<<maxd<<endl; if(ok){ printf("%lld/%lld=",ta,tb); printf("1/%lld",ans[1]); for(int i = 2; i <= maxd; i++){ printf("+1/%lld",ans[i]); } printf(" "); } } return 0; }