埃及分数
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;
}

评论