P1763 埃及分数题解

Mights · 2023-11-17 15:08:38 · 题解

P1763 埃及分数

分析

看完这道题，首选 \text{IDDFS}

可以枚举 S，从 1000 \sim 10^7，每次 S \leftarrow S \times 10

控制搜索深度 \text{maxDep}，表示当前迭代加深搜索的最大深度（即 Code Show 中的 \text{IDDFS}）

上述代码如下：

while (!f)
{
    S = 100, maxDep++;
    while (S < 1e7 && !f)
        S = (S << 3) + (S << 1), f = IDDFS(n, m, 1);
}

我们考虑 \text{IDDFS}

现申请两个大小为 25 的一维数组（足够了），一个叫 res，另一个叫 ans，res 帮忙取答案，ans 则准备输出最后最优的结果，设当前层数为 i

\text{\color{SpringGreen}Optimization \ 1}

如果已经枚举到最后一层（\text{dep = maxDep}），那么 \frac{p}{q} 就只能分成原分式，但是还要判断 a=1 和 b>res_{dep-1}

由于还要保证最后一个分数最大，即分母最小，还要判断 ans 数组已经有了答案，所以接下里就很简单了

如果上述条件都满足，则只需要用 res 记录一下答案，再用 \text{memcpy} 复制一遍就可以了

\text{\color{Blue}Optimization \ 2}

由于分母递增，若前一分母为 p' 需要满足 p>p'，又由于当前分数不能超过剩余部分，故有

\frac{1}{p} \leq \frac{a}{b} \Longrightarrow p \geq \frac{b}{a}

为了能在 \text{maxDep} 层上分解完，须满足

(\text{maxDep}-\text{dep}+1)\ \times \frac{1}{p} \geq \frac{a}{b}

即

p \leq \frac{b(\text{maxDep}-\text{dep}+1)}{a}

考虑进一步紧缩下界

如果 \text{dep}+1=\text{maxDep}，为了保证下一层分母 \frac{1}{\frac{a}{b}-\frac{1}{p}} 依然存在，需满足

\frac{1}{\frac{a}{b}-\frac{1}{p}} \leq S \Rightarrow \frac{bp}{ap-b} \le S \Rightarrow p \geq \frac{Sb}{Sa-b}

类似的在第 i 层需满足

p \geq \frac{Sb}{Sa-(\text{maxDep}-i)b}

综上，

p \in \Big[\max\Big(p',\lceil \frac{b}{a} \rceil,\frac{Sb}{Sa-(\text{maxDep}-i)b}\Big),\min\Big(S,\frac{b(\text{maxDep}-i+1)}{a}\Big)\Big]

\text{\color{SpringGreen}Optimization \ 3}

当仅需枚举两个分母时，设剩余两个分母为 x,y，有

\frac{a}{b}=\frac{1}{x}+\frac{1}{y}

可以得出

\begin{cases}az=x+y\\bz=xy\end{cases} \Rightarrow x^2-azx-bz=0

考虑枚举 z

当 \Delta=a^2z^2-4bz>0 时存在 x \neq y 的解（当 \Delta=0 时 x=y 与规则相悖）

可以得到

x=\frac{az-\sqrt\Delta}{2},y=\frac{az+\sqrt\Delta}{2}

在求解时须验证 \Delta 是否为完全平方数，如果是，令 s=\sqrt\Delta，还需验证 2\ |\ az-s

考虑 z 的枚举上下界

由于 x,y \leq s，那么

az=x+y \le 2S \Rightarrow z \le \frac{2S}{a} \ \ \ \ \ bz=xy\leq S^2 \Rightarrow z \leq \frac{S^2}{b}

同时在求解时 \Delta>0，那么

\Delta=a^2z^2-4bz>0 \Rightarrow z>\frac{4b}{a^2}

综上

z \in \Big[\Big\lfloor\frac{4b}{a^2}+1\Big\rfloor,\min\Big(\frac{2S}{a} \frac{S^2}{b}\Big)\Big]

Code show

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll ans[25], res[25], S;
int n, m, maxDep;
bool f;
bool IDDFS(ll p, ll q, int dep)
{
    if (dep == maxDep)
    {
        if (p == 1 && q > res[dep - 1] && (q < ans[dep] || !ans[dep]))
        {
            res[dep] = q;
            memcpy(ans, res, sizeof(res));
            return true;
        }
        return false;
    }
    if (dep == maxDep - 1)
    {
        for (ll z = (q << 2) / p / p + 1; z < min((S << 1) / p, S * S / q); z++)
        {
            ll delta = p * p * z * z - (q << 2) * z, s = sqrt(delta);
            if (s * s != delta || p * z + s & 1)
                continue;
            res[dep] = p * z - s >> 1, res[dep + 1] = p * z + s >> 1;
            if (res[dep + 1] < ans[dep + 1] || !ans[dep + 1])
            {
                memcpy(ans, res, sizeof(res));
                return true;
            }
        }
        return false;
    }
    ll l = max(res[dep - 1], (q - 1) / p) + 1LL, r = (maxDep - dep + 1) * q / p;
    bool flag = false;
    for (int i = l; i < r; i++)
    {
        ll tx = p * i - q, ty = q * i, g = __gcd(tx, ty);
        res[dep] = i;
        if (IDDFS(tx / g, ty / g, dep + 1))
            flag = true;
    }
    return flag;
}
int main()
{
#ifndef ONLINE_JUDGE
    freopen("data.in", "r", stdin);
    // freopen("data.out", "w", stdout);
#endif
    scanf("%d%d", &n, &m);
    while (!f)
    {
        S = 100, maxDep++;
        while (S < 1e7 && !f)
            S = (S << 3) + (S << 1), f = IDDFS(n, m, 1);
    }
    for (int i = 1; i <= maxDep; i++)
        printf("%lld ", ans[i]);
    return 0;
}

注意

本题解由 stonesx 原著，若有意见请发短信给我，作者将及时处理！

P1763 埃及分数 题解

P1763 埃及分数

分析

Code show

注意

P1763 埃及分数题解