AcWing 1120. 埃及分数
原题链接
中等
作者:
我要出去乱说
,
2021-02-19 12:33:14
,
所有人可见
,
阅读 458
//用迭代加深一层层搜,先搜第一层有没有答案,再搜第二层有没有答案...
#include <iostream>
#include <vector>
using namespace std;
typedef long long LL;
vector<int> ans, path;
LL gcd(LL a, LL b) //辗转相除法模板
{
return b ? gcd(b, a % b) : a;
}
void dfs(LL x, LL y, int last, int t) //last表示下次从哪个数开始搜
{
LL d = gcd(x, y); //求x,y的最大公约数
x /= d, y /= d; //分子分母约分
if (!t) //t用完了且分子x也为0,表示一种可行方案
{
if (!x) //back()表示最后一个分母,要让最大的分母最小
if (ans.empty() || ans.back() > path.back()) ans = path;
return;
}
int down = max(last, (int)((y + x - 1) / x)); //计算上下界
int up = y * t / x;
for (int i = down; i <= up; i ++ ) //分子永远是1不变,分母从小到大搜
{
path.push_back(i);
dfs(i * x - y, y * i, i + 1, t - 1);
path.pop_back();
}
}
int main()
{
int a, b;
cin >> a >> b;
int t = 1;
while (true)
{
dfs(a, b, 1, t); //t为当前剩余个数,至少包含一个分数
if (ans.size()) break;
t ++ ; //每次多搜一个数,迭代加深
}
for (auto x : ans) cout << x << ' ';
return 0;
}
y总这里如果直接写成把down和up的表达式写入for循环就TLE了,for(int i= max(last, (int)((y + x - 1) / x));I<=y * t / x;i)就过不了,直接for(int i=down;i<=up;i)就能AC
我都忘了我是怎么做这个题的了😂兄弟,你连写俩加号的时候要在前边加一个 \ 转义字符,不然一对加号就变成了下划线了呀