传送门

迭代加深搜索是必须的,先枚举加数个数

然后搜索分母

这里有一个强大的剪枝,就是确定分母的范围

#include <cstdio>
#include <cstring>
#define N 100001
#define LL long long
#define min(x, y) ((x) < (y) ? (x) : (y))
#define max(x, y) ((x) > (y) ? (x) : (y)) int n, flag, best = 9999999;
int ans[N], s[N] = {1}; inline void dfs(LL a, LL b, int k)
{
LL i, x, y, l, r;
if(!a)
{
flag = 1;
best = s[n];
for(i = 1; i <= n; i++)
ans[i] = s[i];
return;
}
if(k > n) return;
l = max(s[k - 1] + 1, b / a);
r = min(best - 1, b * (n - k + 1) / a);
for(i = l; i <= r; i++)
if(a * i >= b)
{
x = a * i - b;
y = b * i;
s[k] = i;
dfs(x, y, k + 1);
}
} int main()
{
int i;
LL a, b;
scanf("%lld %lld", &a, &b);
while(!flag)
{
n++;
dfs(a, b, 1);
}
for(i = 1; i <= n; i++)
printf("%d ", ans[i]);
return 0;
}

  

最新文章

  1. 通过docker-machine和etcd部署docker swarm集群
  2. 解决clone问题之外的体会
  3. xmpp4-总览
  4. Day04_JAVA语言基础第四天
  5. for each 循环
  6. RMAN-FORMAT-CONFIGURE及动态性能表
  7. 高频(工作频率为13.56MHz)
  8. Poj 2299 Ultra-QuickSort(归并排序)
  9. GridView点击空白地方事件扩展
  10. ZYNQ-7000 Unable to connect to ps7_cortexa9 解决方案
  11. this与super使用总结(java)
  12. 【开源分享】2018CRM C# 源码(基于小黄豆CRMv2.0.925.3版本功能更新)
  13. JAVA多线程-实现通讯
  14. windows 8.1 cmd命名提示符全屏
  15. 使用Shader制作loading旋转动画
  16. Learning Structured Representation for Text Classification via Reinforcement Learning 学习笔记
  17. css3 媒体查询常用适配
  18. SE Springer小组之《Spring音乐播放器》需求分析说明书一
  19. mysql windows开启客户端连接权限
  20. Android 获取内存信息

热门文章

  1. FPGA的嵌入式RAM
  2. 【Web应用-网络连接】Azure Web 应用对外连接数上限分析
  3. 学习python报错处理
  4. Openjudge 1.13-23:区间内的真素数
  5. tomcat配置 —— 各个目录的作用
  6. dataSource&#39; defined in class path resource [org/springframework/boot/autocon
  7. 兼容IE6\7\8浏览器的html5标签的几个方案
  8. gEdit - GTK+ 基础文本编辑器
  9. winhex与磁盘格式与 数据恢复
  10. 歌乐第二弹:C++九九八十一