题目描述
关于我转生变成史莱姆这档事这部番剧中，上班族的三上悟因为某个事件而作为史莱姆在异世界转生了。在转生时得到了“大贤者”和“捕食者”这两个独特技能。虽然身为史莱姆，但也想和其他种族建立起友好关系。魔素是异世界里面魔物含有的魔力精华，捕食者这个技能就是吞噬魔素，捕食者的技能要求非常苛刻，如果你第一天吞噬了\(b\)魔素，那么你第二天可以吞噬第一天的\(2-9\)倍（必须是其中一个整数），也就是\(2b-9b\)，也就是说，史莱姆在第\(i\)天所吞噬的魔素一定是第\(i-1\)天的\(2-9\)倍，而且还必须是它的整数倍。
作为史莱姆手下的得力助手，哥布林们准备了大量的魔物供主人食用，现在史莱姆已经知道了这些魔物含有\(S\)魔素，现在请大贤者合理安排第一天要吞噬和接下来每天需要增加的魔素倍数，好让史莱姆能在最短的天数内恰好吞噬完魔素。由于大贤者要研究“哲学”，无暇顾及这些小事，现在只能请你帮忙，但是大贤者还建议，这些魔素至少要用两天来吞噬。
输入格式
一个正整数\(S\)，代表要吞噬的魔素总量。
输出格式
一个数，代表要吞噬的天数，如果无解输出\(-1\)。
题目分析
这个题目首先容易观察出是这类整数的题目，那首先列数学式。
$$S=b+k_1b+k_1k_2b+k_1k_2k_3b+k_1k_2……k_{n-1}b$$
$$S=(1+k_1(1+k_2(1+k_3(……(1+k_{n-1})))))b$$
我们会发现里面存在重复性的结构
首先我们枚举所有的b令\(\frac{S}{b}\)为一整数\(a_1\)
接着枚举所有的\(k_1\)令\(\frac{a_1-1}{k_1}\)为一整数\(a_2\)
接着枚举所有的\(k_2\)令\(\frac{a_2-1}{k_2}\)为一整数\(a_3\)
依次类推我们最终可以得到\(a_{n}=1\)即到第\(n\)天全部吃完了，否则说明史莱姆无法正好吃完这一堆食物
需要注意的是枚举的每一步都必须保证是整数解，一旦有一个不满足就直接否定这个路径。
接着就是工具的选择，摆在我们面前深搜和广搜都可行，但是显然我们需要的最有方案，广搜的特性可以保证我枚举完所有当天可行解之后才进入下一天，可以避免出现深搜那种一条道走到黑除非全部枚举不然没有办法得知最优情况的解的情况。
Accepted Code
/*
* @Author: Gehrychiang
* @LastEditTime: 2020-03-15 11:03:23
* @Website: www.yilantingfeng.site
* @E-mail: gehrychiang@aliyun.com
*/
//最多30天
#pragma GCC optimize(2)
#include <bits/stdc++.h>
using namespace std;
int ans = 0x3f3f3f3f;
struct node
{
int day; //当前天数
int qty; //剩余量
};
queue<node> q;
void bfs(int b)
{
q.push({1, b});
while (!q.empty())
{
node tmp = q.front();
q.pop();
if (tmp.qty == 1) //终止条件
{
ans = min(tmp.day, ans);
return;
}
for (int i = 2; i <= 9; i++)
{
if ((tmp.qty - 1) % i == 0) //如果满足解我就压入队列这一个情况进入下一天
{
q.push({tmp.day + 1, (tmp.qty - 1) / i});
}
}
}
}
int main()
{
//freopen("","r",stdin);
//freopen("chk.out","w",stdout);
int n, b;
cin >> n;
int upp = sqrt(n); //从中间位置开始枚举第一天的量
for (int i = upp; i >= 1; i--)
{
if (n % i == 0)
{
b = n / i;
bfs(b);
while (!q.empty()) //清空队列
q.pop();
if (i != b && i > 1) //当然要保证这一天不能全吃也不能只吃一个
{
bfs(i); //同时枚举n/b因为那个也是另一个可行的b
while (!q.empty()) //清空队列
q.pop();
}
}
}
if (ans < 0x3f3f3f3f)
{
cout << ans << endl;
}
else
{
cout << "-1" << endl;
}
//fclose(stdin);
//fclose(stdout);
return 0;
}