题解：P1763 埃及分数

smydahaoren · 2024-06-26 09:57:58 · 题解

思路

这道题目可以使用迭代加深搜索，不过直接搜索肯定是会超时的，所以要做一定的剪枝。

先分析一下搜索的思路。枚举分数从大向小，这样可以保证输出方式是题目要求的顺序（分母从小到大），在枚举完一种情况后，用这种情况储存的数组和最优情况的数组最后一个分母大小进行比较，判断哪一种情况更好。

根据这种想法维护两个数组 ansnow 和 ans。ansnow 用来储存当次枚举的答案，ans 用于纪录目前最优解。now 变量用于储存当次枚举到第几个分数，deep 用于储存总共需要的分数个数。

以下是一些剪枝。

可以限制枚举分母的范围，假设要枚举的分母是 x。显然的，当 a\not= 1 时（当 a=1 时已经进行特判了），\frac{1}{x}<\frac{a}{b}。因此可以推出 x>\frac{b}{a}。所以 x\ge \lfloor \frac{b}{a} \rfloor+1。
又因为根据分母从小到大的顺序。所以 x\ge ansnow_{now-1}+1。
因为可以求出接下来剩下的分数个数为 deep-now+1，并且剩下来的单位分数不应该相等，所以 \frac{a}{b}\times \frac{1}{(deep-now+1)}<\frac{1}{x}。因此 x< \frac{(deep-now+1)\times b}{a}。

剪枝剪完了之后，代码应该是以下这个样子。

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=2e7+9;
int n,m,ans[N],ans1[N];
void turn(int deap){
    for(int i=1;i<=deap;i++)
        ans[i]=ans1[i];
}
int gcd(int aa, int bb) { return bb == 0 ? aa : gcd(bb, aa % bb); }
bool dfs(int now,int a,int b,int deap){
    if(now>deap)
        if(a==0){
            if(ans1[deap]<ans[deap]){
                turn(deap);
            }
            return true;
    }
    else
        return false;
    bool flag=false;
    int q=b/a;
    for(int x=max(q,ans1[now-1]+1);x<=(deap-now+1)*q;x++){
        ans1[now]=x;
        int da=a*x-b;
        int db=b*x;
        int g=gcd(a,b);
        da/=g,db/=g;
        if(dfs(now+1,da,db,deap)) flag=1;
    }

    return flag;

}
signed main(){
    cin>>n>>m;
    int g=gcd(n,m);
    n/=g,m/=g;
    for(int deap=1;;deap++){
        ans[deap]=N;
        if(dfs(1,n,m,deap)==true){
        for(int i=1;i<=deap;i++)
        cout<<ans[i]<<" ";
            break;  
        }
    } 
    return 0;
}

提交后会发现 Hack 数据过不了，原因是因为时间复杂度还是太大了，那么需要更有效的剪枝。

当只剩下最后两个分数枚举时，也就是 now=deep-1 时，因为按照之前的方法枚举量太大，所以导致了超时。

观察 \frac{a}{b}=\frac{1}{x}+\frac{1}{y} 这个式子。经过通分移项后可以得到 \frac{a}{b}=\frac{x+y}{x\times y}。

因此可以得到以下方程：

\begin{cases}x+y=ac\\ x\times y=bc\end{cases}

接下来就相当于接一个一元二次方程 n^2-acn+bc。其中 x 和 y 分别是方程两根。

不妨设 x<y，所以 \begin{cases}x=\frac{ac-\sqrt{(ac)^2-4bc}}{2}\\ y=\frac{ac+\sqrt{(ac)^2-4bc}}{2}\end{cases}。

由此可以得知 (ac)^2-4bc>0。又因为 c 是正整数，所以 c\ge \lfloor \frac{4b}{a^2}\rfloor+1。得知了 c 的下限之后要找到其上限。但是其上限没办法明确得知，因此只能用题目中给出的 10^7。但是这样做还是会超时，如果缩小范围，会导致其他点过不去，因此只能枚举分母的范围 M。

最后只要判断 x,y 是否是正整数即可。

AC 代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e7;
int n,m,ans[11],ansnow[11],M;
bool flag;
void turn(int deep){
    for(int i=1;i<=deep;i++)
        ans[i]=ansnow[i];
}
int gcd(int o, int p) { return p == 0 ? o : gcd(p, o % p); }
void dfs(int now,int a,int b,int deep){
    if(now>deep) return;
    if(a==1){//当到达最简分数时直接返回数值。
        ansnow[now]=b;  
            turn(deep);
        flag=1;
        return;
    }
    if(now == deep - 1){
        int Min=(b*4/a/a)+1,Max=min(2*M/a,M*M/b);
        for(int z=Min;z<=Max;z++){
            int delta=a*a*z*z-4*b*z;
            int Delta=sqrt(delta);
            int tmp=(a*z-Delta)/2;
            if(Delta*Delta!=delta||tmp<=0)
                continue;
            ansnow[now]=(a*z-Delta)/2;ansnow[now+1]=(a*z+Delta)/2;
            if(ansnow[deep]<ans[deep]){
                turn(deep);
                flag=1;
                break;
            }
        }
        return;
    }

    for(int x=max(b/a+1,ansnow[now-1]+1);x<=(deep-now+1)*b/a;x++){  
        ansnow[now]=x;
        int da=a*x-b;
        int db=b*x;
        int g=gcd(da,db);
        da/=g,db/=g;
        dfs(now+1,da,db,deep);
    }
}
signed main(){
    cin>>n>>m;
    int g=gcd(n,m);
    n/=g,m/=g;
    for(int deep=1;;deep++){
        ans[deep]= N + 1;
        for(M=1e5;M<=N;M*=10){
            dfs(1,n,m,deep);
            if(flag){
                for(int i = 1;i <= deep;i++)
                    cout << ans[i] << " ";
                return 0;
            }
        }
    }
    return 0;
}

若本题解出现问题，请私信 smydahaoren。