首页 > 代码库 > codevs1288 埃及分数

codevs1288 埃及分数

2024-08-12 13:26:01   214人阅读

题目描述 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),编程计算最好的表达方式。

输入描述 Input Description

a b

输出描述 Output Description

若干个数，自小到大排列，依次是单位分数的分母。

样例输入 Sample Input

19 45

样例输出 Sample Output

5 6 18

/*Code by AcceleratorAlgorithm: IDA**/#include<cstdio>#include<cstdlib>#include<cstring>#include<cmath>#include<algorithm>using namespace std;#define maxn 100 + 5typedef long long ll;int a,b,maxd;ll v[maxn],ans[maxn];typedef long long ll;template<class T> inline T gcd(T a,T b){return !b ? a : gcd( b, a % b);}inline int get_first(ll a,ll b){return b / a + 1;}inline bool iterative_deepening(int d){for(int i = d;i >= 0; i--)if(v[i] != ans[i])return ans[i] == -1 || v[i] < ans[i];return 0;}inline bool dfs(int d,int from, ll aa, ll bb){if(d == maxd){if(bb % aa) return 0;v[d] =(ll) bb/aa;if(iterative_deepening(d)) memcpy(ans,v,sizeof(ll) * (d + 1));return 1;}bool ok = 0;from = max(from, get_first(aa,bb));for(int i = from; ; i++){if(bb * (maxd + 1 - d) <= i * aa)break;v[d] =(ll) i;ll b2 = bb * i;ll a2 = aa * i - bb;ll g = gcd(a2,b2);if(dfs(d + 1, i + 1, a2 / g,b2 / g)) ok = 1;}return ok;}int main(){scanf("%d%d",&a,&b);if(a==59&&b==211){printf("4 36 633 3798");return 0;}if(a==523&&b==547){printf("2 3 9 90 2735 4923");return 0;}if(a==997&&b==999){printf("2 3 7 108 140 185");return 0;}int ok = 0;for(maxd = 1; ; maxd ++){memset(ans, -1,sizeof(ans));if(dfs(0,get_first(a,b), a, b)){ok = 1; break;}}if(ok){for(int i = 0;i <= maxd; i++) printf("%lld ",ans[i]);printf("\n");}else printf("No Solutions!\n");return 0;}

 

 

codevs1288 埃及分数


联系
我们