题目跳转

Luogu P1763

题目大意

把一个分数，分解为若干个分子为一且分母不同的的和。
最终输出，以分解的个数最小为前提，最小的一个分数的分母最小，即该分数最大。

思路

IDDFS - 剪枝

暴力写的话，IDDFS比较模板，难点在于剪枝。(我认为这个剪枝事实上让这道题有点IDA*的意味了)

题目中说明答案中的分母最大为1e7，然而直接循环是不能接受的。

因此，我们要缩小遍历范围。

下界 —— max(取的上一个数+1,当前相减后剩余的分数的存在的最大的1/x)
上界 —— min(1e7, 剩余的层数都取同一个分母(使得总和与当前的剩余相等)

CODE

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cmath>
#include <cstring>

using namespace std;

typedef long long LL;

const int N = 100010;

struct Node
{
  int up, down;
} a;

int path[N], ans_path[N];
bool flag;

LL gcd(LL a, LL b)
{
  return b ? gcd(b, a % b) : a;
}
Node Node_sub(Node a, Node b) // a-b
{
  LL tx, ty, d;
  ty = (LL)a.down * b.down;
  tx = (LL)a.up * b.down - (LL)b.up * a.down;
  if (!tx)
    return (Node){0, 1};
  d = gcd(tx, ty);
  if (d)
    tx /= d, ty /= d;
  if (!d || ty > (int)1e7 || tx < 0)
    tx = -1;
  if (tx == 0)
    ty = 1;
  return (Node){(int)tx, (int)ty};
}
void dfs(int u, int id, Node remain, int depth)
{
  if (u == depth && remain.up == 0)
  {
    if (!flag || path[u - 1] < ans_path[u - 1])
    {
      memcpy(ans_path, path, sizeof path);
      flag = true;
    }
    return;
  }
  int l = max(id, remain.down / remain.up), r = min(remain.down * (depth - u) / remain.up, (int)1e7); // 强力剪枝 - 缩小范围
  for (int i = l; i <= r; i++)
  {
    Node t = Node_sub(remain, (Node){1, i});
    if (t.up == -1)
      continue;
    path[u] = i;
    dfs(u + 1, i + 1, t, depth);
    path[u] = 0;
  }
}

int main()
{
  ios::sync_with_stdio(0);
  cin.tie(0);
  //   freopen("i.txt", "r", stdin);
  // freopen("o.txt", "w", stdout);
  cin >> a.up >> a.down;
  int depth = 1;
  while (true)
  {
    dfs(0, 2, a, depth);
    if (flag)
      break;
    depth++;
  }
  for (int i = 0; i < depth; i++)
    cout << ans_path[i] << ' ';
  cout << '\n';
  return 0;
}