题解：P1763 埃及分数

· · 题解

前言

这道题的剪枝真的太酷啦（基本上想不到）！

思路

这道题得用迭代加深搜索（IDDFS）。

有以下几种剪枝。

1.假设 \frac{a}{b}=\frac{998}{999}，我们使 \frac{1}{2} + \frac{1}{4} + \frac{1}{8}+\dots=\frac{a}{b}（最差情况），则最多需要 \log_{2}1000 \approx 10 个分数。

2.求分母的左边界。我们知道 \large\frac{1}{p_{idx}} \le \frac{a}{b}，化简得 \large p_{idx} \ge \frac{b}{a}，又因为 p_{idx}\in N_{+}，所以最小的分母为 \max(p_{idx-1}+1,\lceil \frac{b}{a} \rceil)。

3.求分母的右边界。我们知道 \large \frac{1}{p_{idx+1}},\frac{1}{p_{idx+2}} \dots \frac{1}{p_{dep}} < \frac{1}{p_{idx}}、\large\frac{1}{p_{idx}}+\frac{1}{p_{idx+1}}+\frac{1}{p_{idx+2}}+ \dots +\frac{1}{p_{dep}}=\frac{a}{b}，可以得出 \large\frac{dep-idx+1}{p_{idx}} > \frac{a}{b}，化简得 \large p_{idx} \le \frac{(dep-idx+1) \times b}{a}，又因为 p_{idx} \le 10^7 且 p_{idx}\in N_{+}，所以最大的分母为 \min(10^7,\lfloor\frac{(dep-idx+1) \times b}{a}\rfloor)。

4.如果已经有结果了，那么最大分母为 \min(\min(10^7,\lfloor\frac{(dep-idx+1) \times b}{a}\rfloor),p_{dep}-1)。

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const LL N=1e7;
LL a,b,q[11],p[11];
int dep;
bool flag=false;
LL gcd(LL x,LL y){//最大公约数 
    return y==0?x:gcd(y,x%y);
}
void dfs(LL a,LL b,int idx){
    if(idx>dep) return;//超出所规定的深度，返回 
    if(a==1){ 
        if(b>p[idx-1]){//判断分母是否大于上一个分母 
            p[idx]=b;
            if(!flag||p[idx]<q[idx]){//如果没有答案 或者 现在最后一个分母比上一个答案的最后一个分母小 
                for(int i=1;i<=idx;i++) q[i]=p[i];//赋值 
                flag=true;//已经有答案 
            }
        }
        return;
    }
    LL lf=max(p[idx-1]+1,(a+b-1)/a),rt=min(N,(dep-idx+1)*b/a);//剪枝2、3 
    if(flag&&rt>=p[dep]) rt=p[dep]-1;//剪枝4 
    for(LL i=lf;i<=rt;i++){//枚举分母 
        p[idx]=i;
        LL son=a*i-b,mth=b*i;
        LL k=gcd(mth,son);
        dfs(son/k,mth/k,idx+1);
    }
}
int main(){
//  freopen(".in","r",stdin);
//  freopen(".out","w",stdout);
    scanf("%lld%lld",&a,&b);
    LL c=gcd(a,b);
    a/=c,b/=c;//先给分数化简 
    p[0]=1;
    for(dep=1;dep<11;dep++){//枚举深度，剪枝1 
        dfs(a,b,1);
        if(flag){//如果有结果，直接输出 
            for(int i=1;i<=dep;i++) printf("%lld ",q[i]);
            return 0;
        }
    }
    return 0;
}

到这里就可以拿 100 分了，但是邪恶的 hack 数据会超时。所以还要剪枝。

5.我们还可以枚举最大分母的大小，建议 N 从 10^5 开始，每次乘 10（不知道是作者代码原因还是其他，如果 N 从 10^3 或者 10^4 开始会 WA）。

for(dep=1;dep<11;dep++){//枚举深度 
        for(N=1e5;N<=1e7;N*=10){//枚举分母范围，剪枝5
            dfs(a,b,1);
            if(flag){//如果有结果，直接输出 
                for(int i=1;i<=dep;i++) printf("%lld ",q[i]);
                return 0;
            }
        }
    }

6.最后一个剪枝就厉害了。当我们搜索到倒数第二个分数时，可以进行特殊处理。此时 \large \frac{a}{b}=\frac{1}{p}+\frac{1}{q}=\frac{p+q}{p \times q}。

设\large\begin{cases} p+q=a \times k \\ p \times q=b \times k \end{cases} ，k \in N_{+}

通过第一条式子可以得出 q=a \times k-p，将其带入第二条式子，得 p \times (a \times k-p)=b \times k，化简得 p^2-a \times k \times p+b \times k=0，则 \varDelta=a^2 \times k^2-4 \times b \times k \ge 0，解一元二次不等式的过程如下：

因为 k\in N_{+}，所以 k\ge\lceil\frac{4 \times b}{a^2}\rceil。

根据公式可得 p=\frac{a \times k \pm \sqrt{\varDelta}}{2}，要求 p\in N_{+}，\varDelta 为完全平方数且 2\mid a \times k \pm \sqrt{\varDelta}（判断一种情况就行了）。得出的解 p_1、p_2即为最后两个分母。

最后一步就是要求 k 的取值范围了，我们已经求出 k\ge\lceil\frac{4 \times b}{a^2}\rceil，还需要求 k 的右边界。已知 p_1+p_2=a \times k，因为 p_1<p_2\le N（N为最大能取的分母），所以 a \times k<2 \times N，化简得 k<\frac{2 \times N}{a}，又因为 k \in N_{+}，所以 k \le \lfloor\frac{2 \times N}{a}\rfloor；已知 p_1 \times p_2=b \times k，p_1<p_2\le N，所以 a \times k \le N \times (N-1)，化简得 k \le \frac{N \times (N-1)}{a}，又因为 k \in N_{+}，所以 k \le \lfloor\frac{N \times (N-1)}{a}\rfloor。所以综上所述，k=\min(\lfloor\frac{2 \times N}{a}\rfloor,\lfloor\frac{N \times (N-1)}{a}\rfloor)。

AC 代码

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
LL a,b,q[11],p[11],N;
int dep;
bool flag=false;
LL gcd(LL x,LL y){//最大公约数 
    return y==0?x:gcd(y,x%y);
}
void dfs(LL a,LL b,int idx){
    if(idx>dep) return;//超出所规定的深度，返回 
    if(a==1){
        if(b>p[idx-1]){//判断分母是否大于上一个分母 
            p[idx]=b;
            if(!flag||p[idx]<q[idx]){//如果没有答案 或者 现在最后一个分母比上一个答案的最后一个分母小 
                for(int i=1;i<=idx;i++) q[i]=p[i];//赋值 
                flag=true;//已经有答案 
            }
        }
        return;
    }
    if(idx==dep-1){//剪枝6 
        LL lf=(b*4/(a*a))+1,rt=min(2*N/a,N*(N-1)/b);
        for(LL i=lf;i<=rt;i++){
            LL d=a*a*i*i-4*b*i;
            LL k=sqrt(d);
            if(k*k!=d||((a*i-k)&1)) continue;
            p[idx]=(a*i-k)>>1;
            p[dep]=(a*i+k)>>1;
            if(p[idx]<=p[idx-1]||p[dep]<=p[idx]) continue;
            if(!flag||p[dep]<q[dep]){
                for(int j=1;j<=dep;j++) q[j]=p[j];
                flag=true;
            }
        }
        return;
    }
    LL lf=max(p[idx-1]+1,(a+b-1)/a),rt=min(N,(dep-idx+1)*b/a);//剪枝2、3 
    if(flag&&rt>=p[dep]) rt=p[dep]-1;//剪枝4 
    for(LL i=lf;i<=rt;i++){//枚举分母 
        p[idx]=i;
        LL son=a*i-b,mth=b*i;
        LL k=gcd(mth,son);
        dfs(son/k,mth/k,idx+1);
    }
}
int main(){
//  freopen(".in","r",stdin);
//  freopen(".out","w",stdout);
    scanf("%lld%lld",&a,&b);
    LL c=gcd(a,b);
    a/=c,b/=c;//先给分数化简 
    p[0]=1;
    for(dep=1;dep<11;dep++){//枚举深度，剪枝1 
        for(N=1e5;N<=1e7;N*=10){//枚举分母范围，剪枝5 
            dfs(a,b,1);
            if(flag){//如果有结果，直接输出 
                for(int i=1;i<=dep;i++) printf("%lld ",q[i]);
                return 0;
            }
        }
    }
    return 0;
}

结尾

我从来没有做过剪枝这么巧妙的题。这道题花费了我一天的时间，虽然还有其他剪枝没写，但是收获也很大。希望大家多刷刷有挑战的题，长长见识，增长才干，在赛场上取得优异成绩！