埃及分数 Time Limit:2s Memory Limit:1000k Total Submit:2302 Accepted:340 下载样例程序(PE) 下载样例程序(ELF) -------------------------------------------------------------------------------- Problem 在古埃及，人们使用单位分数的和(形如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 第一行:N 表示有N组测试数据，每组测试数据为一行包含a,b(0〈a〈b〈1000)。 Output 每组测试数据若干个数，自小到大排列，依次是单位分数的分母。 Sample Input 1 19 45 Sample Output 5 6 18 Source oibh #include <iostream> #include <algorithm> #include <cstdlib> #include <cmath> #include <iomanip> using namespace std; const double zero=1e-20; const double maxn=1e20; int num; bool bb; double tempa[1000],tempb[1000],best[1000],v[1000]; int g_cd(int a,int b) {     int ta,tb;     ta=a;tb=b;     if(ta<tb)swap(ta,tb);     if(!(ta%tb))return tb;     else return g_cd(tb,ta%tb); } void solve(int x) {     int i,next,temp,prev;     if(x>num)     {         if(fabs(tempa[num])<zero)         {                 bb=1;                 if(v[num]<best[num])                  for(i=1;i<=num;i++)                     best[i]=v[i];         }     }else     {         prev=(int(tempb[x-1]/tempa[x-1])>int(v[x-1]+1))?int(tempb[x-1]/tempa[x-1]):int(v[x-1]+1);         next=int((num-x+1)*tempb[x-1]/tempa[x-1]+zero);         if(tempb[x-1]/tempa[x-1]+num-x+1>best[num])return;         for(i=prev;i<=next;i++)         {             v[x]=i;             tempa[x]=tempa[x-1]*i-tempb[x-1];             if(tempa[x]<0)continue;             tempb[x]=tempb[x-1]*i;             if(tempa[x]>-zero && int(tempa[x]*v[x]/tempb[x])<=num-x)               solve(x+1);         }     } } int main(int argc, char *argv[]) {     int i,j,n,temp,a,b;     cin>>n;     for(j=0;j<n;j++)     {         cin>>a>>b;         temp=g_cd(a,b);         a/=temp;b/=temp;         if(a==1)               cout<<b<<endl;         else         {                 v[0]=b/a;num=1;                 bb=0;best[1]=maxn;                 while(1)                 {                     num++;                     best[num]=maxn;                     tempa[0]=a;tempb[0]=b;                     solve(1);                     if(bb)break;                 }                 for(i=1;i<num;i++)                     cout<<setiosflags(ios::fixed)<<setprecision(0)<<best[i]<<' ';                 cout<<best[num]<<endl;         }     }     //system("PAUSE");         return 0; }

评论