https://loj.ac/problem/10022

题目描述

  对于形如1/n (n为正整数)称为单位分数,给出a和b,求最少可用几个单位分数表示,给出方案。

思路

  这道题的难点主要在于对分数的处理和枚举边界的决定。首先我们先可以确定dfs的大致框架和dfs的内容。由于一个分数有无数多种拆分方式,而我们需要的仅仅是长度最短和最小分数最大的方案,因此可以采用迭代加深搜索,枚举这个分数由几个单位分数组成。所以我们的dfs需要存储这几个信息:当前枚举到第几个答案,枚举的下界,用p和q两个变量存储分数。我们先考虑最初的枚举下界,显然,如果a|b,那么可直接输出答案;否则,我们可以从a/b+1开始枚举,因为这是小于它的最大单位分数。所以我们可以每一次都处理一遍p/q的下界,枚举每个单位分数,再减去该单位分数进行枚举。不过我们还未处理其上界,显然,如果剩下的所有数都为1/i和都达不到p/q就可以结束循环。

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll s[10100],ans[10100],lim;
ll gcd(ll a,ll b)
{
    return a%b==0?b:gcd(b,a%b);
}
bool check()
{
/*    for(ll i=lim;i>0;i--)
        printf("%lld ",s[i]);
    printf("\n");*/
    for(ll i=lim;i>0;i--)
        if(s[i]!=ans[i])return ans[i]==-1||s[i]<ans[i];
    return 0;
}
bool dfs(ll dep,ll from,ll p,ll q)
{
    if(dep==lim)
    {
        if(q%p!=0)return 0;
        s[dep]=q/p;
        if(check())
        {
            for(int i=1;i<=dep;i++)
                ans[i]=s[i];
        }
        return 1;
    }
    else
    {
        bool f=0;
        from=max(from,q/p+1);
        for(ll i=from;;i++)
        {
            if(q*(lim+1-dep)<=i*p)break ;
            s[dep]=i;
            ll pp=p*i-q;
            ll qq=q*i;
            ll g=gcd(pp,qq);
            if(dfs(dep+1,i+1,pp/g,qq/g))f=1;
        }
        return f;
    }

}
int main()
{
    ll a,b;
    scanf("%lld%lld",&a,&b);
    if(b%a==0)
        printf("%lld",b/a);
    else
    {
        for(lim=1;;lim++)
        {
            memset(ans,-1,sizeof(ans));
            if(dfs(1,b/a+1,a,b))break ;
        }
        for(ll i=1;i<=lim;i++)
            printf("%lld ",ans[i]);
    }
    return 0;
}
01-22 06:30