P1763 埃及分数

发表于 分类于 阅读次数： Waline： 本文字数： 1.2k 阅读时长 ≈ 4 分钟

考点

  • 迭代加深
  • 剪枝
  • 最大公约数

题解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e3 + 50;
ll depth, path[maxn], ans[maxn];
bool flag;

ll gcd(ll a, ll b) { return b ? gcd(b, a % b) : a; }

void dfs(ll a, ll b, ll d) {
  // 倒数第二位和倒数第一位优化
  if (d == depth - 1) {
    ll k = 4 * b / (a * a);
    for (;; ++k) {
      double delta = a * a * k * k - 4 * b * k;
      ll t = sqrt(delta), r = -1;
      // 如果开根号后，t是整数，说明有整数解
      if (t * t == delta)
        r = t;
      else if ((t - 1) * (t - 1) == delta)
        r = t - 1;
      else if ((t + 1) * (t + 1) == delta)
        r = t + 1;
      ll x = (a * k - r) / 2, y = (a * k + r) / 2;
      // 大于1e7，退出
      if (y > 1e7) break;
      // 最优性剪枝：当前的b比答案最小值都小，退出
      if (flag && y >= ans[depth]) break;
      // 可行性剪枝：没有整数解或者两个解相同，剪枝
      if (r <= 0) continue;
      // 可行性剪枝：x和y必须都是整数
      if ((a * k + r) & 1) continue;
      // 记录答案
      path[d] = x, path[d + 1] = y;
      for (int i = 1; i <= depth; ++i) ans[i] = path[i];
      flag = 1;
    }
    return;
  }
  // 优化搜索顺序：从大到小
  ll l = max(b / a + 1, path[d - 1] + 1);
  ll r = min((ll)1e7, (depth - d + 1) * b / a);
  // 最优性剪枝：如果有答案，则以答案为上限
  if (flag) r = min(r, ans[depth] - 1);
  for (ll i = l; i <= r; ++i) {
    path[d] = i;
    // 每次都要约分，因为a和b运算后不一定是最简
    ll ta = a * i - b, tb = b * i, g = gcd(ta, tb);
    dfs(ta / g, tb / g, d + 1);
  }
}

int main() {
  ll a, b;
  cin >> a >> b;
  ll g = gcd(a, b);
  a /= g, b /= g, path[0] = 1;
  depth = 1;
  while (1) {
    dfs(a, b, 1);
    if (flag) {
      for (int i = 1; i <= depth; ++i) cout << ans[i] << " ";
      break;
    }
    ++depth;
  }
  return 0;
}

思路

根据题意：

  • 加数少的比加数多的好

    选择迭代加深，控制枚举位数

  • 加数个数相同的，最小的分数越大越好

    枚举每一位置的分数时，从大到小枚举优化搜素顺序

    因为很显然，大数中找最大值与小数中找最大值，显然前者可能性更大

在这里，不要妄想同时枚举分子和分母，因为最大范围有1e7，是天文数字；只考虑枚举分母即可

分母的下界

在枚举分母之前一定要对a / b进行约分保证最简

假设当前有a / b，需要将其转换为1 / i

由于a / b已经约分后最简了，那么必然有： \[ \frac{a}{b}>\frac{1}{i}\Rightarrow i>\frac{b}{a} \] 又因为我们是从大到小枚举，且题目声明分母不准相同，那么本次的分母i应该大于上一次的分母： \[ i>path\left[ d-1 \right] \] 所以得到分母的下界：

1
ll l = max(b / a + 1, path[d - 1] + 1);

分母的上界

因为1 / i小于a / b，那么肯定还有剩余，剩余部分就作为下一次递归的输入；

算上当前位置，最多还有depth - d + 1个位置，而后续每个位置的分母必大于i，取极值的话，必有： \[ \frac{1}{i}\cdot \left( depth-d+1 \right) \leqslant \frac{a}{b} \] 由于题目要找最小值的最大，假设当前i都比ans[depth]都大，说明1 / i比答案都小，那么直接用答案来剪枝即可

最终得到了上界

1
2
3
ll r = min((ll)1e7, (depth - d + 1) * b / a);
// 最优性剪枝：如果有答案，则以答案为上限
if (flag) r = min(r, ans[depth] - 1);

递归输入

综上，因为1 / i必小于a / b，所以还有剩余，剩余部分的分子就等于a * i - b，分母就等于b * i

得到如下代码：

1
2
3
4
5
6
for (ll i = l; i <= r; ++i) {
  path[d] = i;
  // 每次都要约分，因为a和b运算后不一定是最简
  ll ta = a * i - b, tb = b * i, g = gcd(ta, tb);
  dfs(ta / g, tb / g, d + 1);
}

答案

枚举到最后两位时，考虑用数学进行优化 \[ \frac{ak}{bk}=\frac{1}{x}+\frac{1}{y} \] 倒数第二位置的分母为x，倒数第一位置的分母为y，消去y后得到二元一次不等式 \[ \begin{cases} ak=x+y\\ bk=xy\\ \end{cases}\Rightarrow x^2-akx+bk=0 \] 那么可以通过枚举k，通过求根公式得到x和y的值；由于题目说了不能有重复分母，可以得到k的范围： \[ \varDelta =a^2k^2-4bk>0\Rightarrow k>\frac{4b}{a^2} \] 令\(\sqrt{a^2k^2-4bk}\)为r，根据求根公式： \[ \frac{ak\pm \sqrt{a^2k^2-4bk}}{2} \] 得到x = (a * k - r) / 2，y = (a * k + r) / 2

需要满足以下条件即可：

  • y < 1e7
  • r是整数且大于0，小于0说明无解，等于0说明两根相同
  • (a * k - r)可以整除2，保证x和y都是整数