P1763 题解

tangtianyao0123 · 2025-09-13 22:37:48 · 题解

这是五年级蒟蒻的第一篇题解，望管理员通过

题目传送门

分析

对于 \frac{a}{b}，要求把他拆成 \frac{1}{x_1} + \frac{1}{x_2} + ... + \frac{1}{x_n}，其中：

x_1, x_2...x_n \in Z
在满足 2 条件时，x_n 最小
思路
不能贪心：
因为可能在选取数后剩下的数无法分拆
不能广搜：
在记录状态时空间会爆
不能深搜：
深搜可能无底洞的搜下去，暴时间

那怎么办呢？
我要介绍一种新东西：迭代加深搜索

迭代加深搜索（IDDFS）

迭代加深搜索本质是深搜，但他限定了深度，一旦当前搜索深度大于或等于限定深度，就立刻回溯，如果当前限制的深度有答案有直接结束，如果没有就放宽限制
所以伪代码大概长这样：

void dfs(int dep, ...){//dep表示当前深度
  if(dep > maxdep) return ;
  if(dep == maxdep){
    //do sth
    return ;
  }
  for(/*当前状态转移出的新状态y*/){
    dfs(dep + 1, y);
  }
}
int main(){
  ...
  for(maxdep = 1; ; maxdep++){
    dfs(0, ...);
    if(有结果){
      //do sth
      return 0;
    }
  }
}

有人就会问：在限定新深度时，浅深度的状态会被枚举很多次，会不会浪费时间导致 T 飞？
我的回答是：这个得具体情况具体分析，当一个状态能转移出的状态不多时，在枚举新限定深度时，需要记录上一层状态；但如果转移状态是指数级的增长时，就没必要，因为前几层的状态在后几层来说就是九牛一毛，记状态也快不了多少。

迭代加深弥补了广搜的空间开销太大，也弥补了深搜的无底洞

对于每次转移，就是在剩下的 \frac{a}{b} 中枚举 i，将其减去 \frac{1}{i}，由于 i 严格递增，所以，我们需要记录 i 的上一个，所以状态如下：

dfs($当前深度，所剩分子，所剩分母，上一个选的数$)

对于 i，他不仅要大于上一个选的数，而且得使减完后的数大于或等于 0，所以 i>\max(\text{last}+1, \lceil\frac{b}{a}\rceil) 所以很容易写出以下~~样例都过不了的~~代码

#include <bits/stdc++.h>
#define int long long

using namespace std;

int a, b, dep;
vector<int> v, ans;
bool f;

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

void dfs(int x, int a, int b, int l){
  if(x == dep){
    if(!a){
      if(ans.empty() || v.back() < ans.back()){
        ans = v;
      }
      f = 1;
    }
    return ;
  }
  for(int i = max(l + 1, (b + a - 1) / a); i <= 1e7; i++){
    int d = gcd(a * i - b, i * b);
    v.push_back(i);
    dfs(x + 1, (a * i - b) / d, i * b / d, i);
    v.pop_back();
  }
}

signed main(){
  cin >> a >> b;
  int x = gcd(a, b);
  a /= x, b /= x;
  for(dep = 1; ; dep++){
    dfs(0, a, b, 1);
    if(f){
      for(int x : ans){
        cout << x << ' ';
      }
      break;
    }
  }
  return 0;
}

我们需要优化

剪枝1

对于没一次枚举 i，一共还需要减 maxdep - dep + 1 个数，这些数之和小于 (maxdep - dep + 1) \times \frac{1}{i}，而这些数之和应该小于所剩的 \frac{a}{b}，所以我们考虑可行性剪枝，同时，所剩的 \frac{a}{b} 也应该大于 \frac{1}{10^7}

剪枝2

枚举最后一层工作量极大，可以直接求。
根据前面两个剪枝，可以写出以下代码

#include <bits/stdc++.h>
#define int long long

using namespace std;

int a, b, dep, cnt = 0;
vector<int> v, ans;
bool f;

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

void dfs(int x, int a, int b, int l){
  if(x == dep - 1){
    if(a == 1){
      if(b > v.back()){
        v.push_back(b);
        if(ans.empty() || v.back() < ans.back()){
          ans = v;
        }
        v.pop_back();
        f = 1;
      }
    }
    return ;
  }
  for(int i = max(l + 1, b / a); i <= 1e7 && a * i < (dep - x + 1) * b; i++){
    int d = gcd(a * i - b, i * b);
    v.push_back(i);
    if((a * i - b) / d * 1e7 >= i * b / d){
      dfs(x + 1, (a * i - b) / d, i * b / d, i);
    }
    v.pop_back();
  }
}

signed main(){
  cin >> a >> b;
  int x = gcd(a, b);
  a /= x, b /= x;
  for(dep = 1; dep < 11; dep++){
    dfs(0, a, b, 1);
    if(f){
      for(int x : ans){
        cout << x << ' ';
      }
      break;
    }
  }
  return 0;
}

然后就会获得 hack数据TLE 的拥抱
~~如果你只想练习迭代加深，那你可以走了~~

剪枝3

考察最后两层搜索，它们占了主要的时间。

我们想要知道 \frac{a}{b} = \frac{1}{x_1} + \frac{1}{x_2}(x_1 < x_2) 的整数解，通分得 \frac{a}{b} = \frac{x_1 + x_2}{x_1x_2} ，又因为 \gcd(a,b) = 1，所以存在正整数 k，使

ak = x_1+x_2 \hspace{1cm} (1) \\ bk = x_1x_2 \hspace{1cm} (2) \end{cases}

(1) \times x_1$ 得 $akx_1 = x_1^2 + x_1x_2

将 (2) 代入，得 x_1^2 - akx_1 + bk = 0

\Delta = a^2k^2 - 4bk = k(a^2k-4b) \ge 0

又因为 k \ge 0，所以 a^2k - 4b \ge 0，即 k \ge \displaystyle \lceil \frac{4b}{a^2} \rceil，所以

x_1 = \frac{4b + \sqrt{\Delta}}{2}\\ x_2 = \frac{4b - \sqrt{\Delta}}{2} \end{cases}

同时得保证，x_1,x_2\in \Z，所以 \sqrt{\Delta} \in \Z,2 \mid 4b + \sqrt{\Delta}
为什么不管 x_2 呢？
因为 4b + \sqrt{\Delta} 与 4b - \sqrt{\Delta} 同奇偶。

所以我们得枚举 k，直到 x_2 > 10^7 或不比当前答案更优时退出。

AC代码

理解第一，理解第一，理解第一

#include <bits/stdc++.h>
#define int long long

using namespace std;

int a, b, dep;
vector<int> v, ans;
bool f;

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

void dfs(int x, int a, int b, int l){
  if(x == dep - 2){
    int mi = (4 * b + a * a - 1) / (a * a);
    for(int k = mi; ; k++){
      int delta = a * a * k * k - 4 * b * k, sd = sqrt(delta), t = -1;
      if(sd * sd == delta) t = sd;
      else if((sd - 1) * (sd - 1) == delta) t = sd - 1;
      else if((sd + 1) * (sd + 1) == delta) t = sd + 1;
      int x1 = (a * k - t) / 2, x2 = (a * k + t) / 2;
      if(x2 > 1e7 || f && x2 >= ans.back()) break;
      if(t <= 0 || (a * k + t) % 2 != 0 || x1 <= l) continue;
      v.push_back(x1);
      v.push_back(x2);
      ans = v;
      v.pop_back();
      v.pop_back();
      f = 1;
    }
    return ;
  }
  for(int i = max(l + 1, (b + a - 1) / a); i <= 1e7 && a * i < (dep - x + 1) * b; i++){
    int d = gcd(a * i - b, i * b);
    v.push_back(i);
    if(i <= 1e7 && (a * i - b) / d * 1e7 >= i * b / d){
      dfs(x + 1, (a * i - b) / d, i * b / d, i);
    }
    v.pop_back();
  }
}

signed main(){
  cin >> a >> b;
  int x = gcd(a, b);
  a /= x, b /= x;
  if(a == 1) return cout << b, 0;
  for(dep = 2; dep <= 11; dep++){
    dfs(0, a, b, 1);
    if(f){
      for(int x : ans){
        cout << x << ' ';
      }
      break;
    }
  }
  return 0;
}

P1763 题解

分析

思路

迭代加深搜索（IDDFS）

剪枝1

剪枝2

剪枝3

AC代码