题解：P1763 埃及分数

· · 题解

还能交题解肯定得蹭啊。

发现给的题面较为困难，于是直接考虑爆搜，但是这样深搜显然超时，而宽搜状态数会超内存，故而进行迭代加深搜索（即逐层提高限制进行深搜）以降低复杂度。

枚举 dep 为组成 \frac a b 的分数个数，令其从小到大递增，每次执行 dfs 即可。接下来讨论 dfs 的内部实现。

我们记 \{ans\} 和 \{st\} 分别表示当前的最优解分母与目前搜到的分母序列。那么设当前分母为 x，搜了 y 个分母，显然有 \frac 1 x \le \frac a b 即 x \ge \left \lceil \frac b a \right \rceil，又有 x \le st_{y - 1} 和 \frac 1 x \cdot (dep - y + 1) \ge \frac a b（也即若以后的分母全都等于 x 必须大于 \frac a b），那么得到了一个大致的搜索范围。

但是这样做还是太粗糙了，无法通过，考虑更加精细的搜索。

首先当 y = dep 时只有 a = 1 且 b > st_{y - 1} 才有解，这一点是好做的，可以反过来判断。

其次，当 y = dep - 1 时只剩两个分数，我们也可以进行简化：假设当前剩下的分数为 \frac {a'} {b'}（最简），加上的两个分母分别为 n、m，则有 \frac {a'} {b'} = \frac 1 n + \frac 1 m = \frac {n + m} {nm}。这其中可能存在约分，故记 n + m = ka'，nm = kb'，以 n 建立等式关系得到 m ^ 2 - a'km + b'k = 0，\Delta = (a') ^ 2 k ^ 2 - 4 b'k = k [(a') ^ 2 k - 4 b'] 需非负，所以 k \ge \left \lceil \frac {4 b'} {(a') ^ 2} \right \rceil，那么得到了枚举下界。最后算得 \sqrt \Delta 后代入得到 n 与 m 再判断合法性即可。

注意为了得到最简的分数每次搜索需要约分。

:::success[code]

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1e7;
int dep = 1, st[11], ans[11], f;
int gcd(int a, int b){
    if (!a || !b)return a | b;
    int az = __builtin_ctzll(a), bz = __builtin_ctzll(b), z = az < bz ? az : bz;
    a >>= az;
    do{
        b >>= bz;
        if (a > b){int t = a;a = b, b = t;}
        b -= a, bz = __builtin_ctzll(b);
    }while (b);
    return a << z;
}void dfs(int a, int b, int x){
    if (x > dep)return;
    if (a == 1 && b > st[x - 1]){
        st[x] = b;
        if (!f || b < ans[dep])
            for (int i = 1; i <= dep; i ++)ans[i] = st[i];
        f = 1;return;
    }if (x == dep - 1){
        for (int i = ceil(4.0 * b / a / a); ; i ++){
            int z = a * i, d = z * z - 4 * b * i, t = sqrt(d), g = -1;
            if (t * t == d)g = t;else if ((t - 1) * (t - 1) == d)g = t - 1;
            else if ((t + 1) * (t + 1) == d)g = t + 1;
            int k = z - g >> 1, y = z + g >> 1;
            if (y > N || (f && y >= ans[dep]))break;
            if (g <= 0 || (z + g & 1))continue;
            st[dep - 1] = k, st[dep] = y;
            if (!f || y < ans[dep]){
                for (int i = 1; i <= dep; i ++)ans[i] = st[i];
                f = 1;
            }break;
        }return;
    }int l = max((b + a - 1) / a, st[x - 1] + 1), r = (dep - x + 1) * b / a;
    if (f && r >= ans[dep])r = ans[dep] - 1;r = min(r, N);
    for (int i = l; i <= r; i ++){
        st[x] = i;
        int num = a * i - b, den = b * i, g = gcd(abs(num), den);
        dfs(num / g, den / g, x + 1);
        if (f && i >= ans[dep])break;
    }
}signed main(){
    int a, b, c;
    cin >> a >> b, c = gcd(a, b), a /= c, b /= c, st[0] = 1;
    for (dep = 1; ; dep ++){
        f = 0, dfs(a, b, 1);
        if (f){
            for (int i = 1; i <= dep; i ++)cout << ans[i] << " ";
            return 0;
        }
    }return 0;
}

:::

鸣谢：感谢 HITUO 提供了代码基础框架和调题动力，HRPA 提供了 gcd 板子，具体的开根做法参考了此篇题解。