64 lines
1.7 KiB
C++
64 lines
1.7 KiB
C++
#include <bits/stdc++.h>
|
|
using namespace std;
|
|
|
|
vector<int> best_solution; // 当前最优解
|
|
int best_max_den = INT_MAX; // 当前最优解的最大分母
|
|
|
|
// gcd 辅助函数
|
|
long long gcd(long long a, long long b) {
|
|
return b == 0 ? a : gcd(b, a % b);
|
|
}
|
|
|
|
// DFS 搜索埃及分数
|
|
void dfs(vector<int>& path, int step, int max_depth,
|
|
long long num, long long den, int a, int b, int start) {
|
|
if(step > max_depth) return;
|
|
|
|
if(num * b == den * a) {
|
|
int cur_max = *max_element(path.begin(), path.end());
|
|
if(best_solution.empty() || cur_max < best_max_den) {
|
|
best_solution = path;
|
|
best_max_den = cur_max;
|
|
}
|
|
return;
|
|
}
|
|
|
|
// 下限剪枝
|
|
long long i_start = max((long long)start, (den + num - 1) / num); // ceil(den/num)
|
|
for(long long i = i_start; i <= 15000; i++) {
|
|
path.push_back(i);
|
|
long long new_num = num * i + den;
|
|
long long new_den = den * i;
|
|
long long g = gcd(new_num, new_den);
|
|
new_num /= g;
|
|
new_den /= g;
|
|
if(new_num * b <= new_den * a) { // 剪枝
|
|
dfs(path, step + 1, max_depth, new_num, new_den, a, b, i + 1);
|
|
}
|
|
path.pop_back();
|
|
}
|
|
}
|
|
|
|
// IDS 主函数
|
|
vector<int> egyptian_fraction(int a, int b) {
|
|
best_solution.clear();
|
|
best_max_den = INT_MAX;
|
|
|
|
for(int depth = 1; depth <= 15000; depth++) { // 最大深度可调
|
|
vector<int> path;
|
|
dfs(path, 0, depth, 0, 1, a, b, 1);
|
|
if(!best_solution.empty()) break; // 找到最短长度解
|
|
}
|
|
return best_solution;
|
|
}
|
|
|
|
int main() {
|
|
int a, b;
|
|
cin >> a >> b;
|
|
vector<int> res = egyptian_fraction(a, b);
|
|
for(int x : res) cout << x << " ";
|
|
cout << endl;
|
|
return 0;
|
|
}
|
|
|