赛后题解——问题 D: 游戏jienzi（记忆化）数据结构与算法qq45739057的博客-

注释：多组测试数据卡超时不多的话可以试试这题能否用数组记录，这样有的数据就可以
$small O(1)$

O(1)时间算出

问题 D: 游戏jienzi
题目描述

Brother Jien 发明了一个有趣的游戏。
一开始你有一个数 S，接着呢，Jien 会按照自己的喜好给你 T 个 x，这时你要进行若干轮操作，第 i 轮（如果有）令 S−=x,之后让 x∗=pi。其中 pi是一个由你决定的，从二到九的一个整数。你要做的是用最少轮数令 S=0 。由于Jien 不保证对于每个 x 一定有解，所以无解时你应输出”Orz Brother Jien!”来表达你的敬意。

输入

第一行两个正整数 S , T ，含义如题所述。
接下来 T 行，每行一个数 x ，表示一个询问，由于 Jien 哥随性自由，所以保证由他出的数据在各个合法范围内纯随机生成。

输出

T 行，一行一个整数，表示最少的操作次数。
如果无解，请表达你对Brother Jien 的敬意。

样例输入

15 2
5
4

样例输出

2
Orz Brother Jien!

提示

对于
$small 100$

100% 的数据 有
$small T≤5times10^5$

T≤5×105,
$small x≤S≤10^8$

x≤S≤108。

解决思路：由题意可以得到，有解的充要条件是
$small S=x+k_1x+k_2k_1x+…+k_n…k_2k_1x$

S=x+k1​x+k2​k1​x+...+kn​...k2​k1​x，其中
$small 2leq k_i leq 9$

2≤ki​≤9。
观察式子，发现只要
$small S$

S不是
$small x$

x的倍数，就必然无解。
考虑
$small S$

S是
$small x$

x的倍数的情况，将式子两边都除以
$small x$

x

$small therefore largefrac{S}{x}small=1+k_1+k_2k_1+…+k_n…k_2k_1$

∴xS​=1+k1​+k2​k1​+...+kn​...k2​k1​
再进行变换，提出公因式

$small therefore largefrac{S}{x}small=1+k_1(1+k_2(…(1+k_{n-1}(1+k_n))…))$

∴xS​=1+k1​(1+k2​(...(1+kn−1​(1+kn​))...))
这个式子就可以直接
$small dfs$

dfs判断了，枚举
$small k_i$

ki​
$small (2leq k_i leq 9)$

(2≤ki​≤9)，枚举的时候如果这个
$small k_i$

ki​是
$small now-1$

now−1的因子的话，就深搜记录最小值，否则不用管。
这道题的恶心之处在于多组测试数据，如果强行直接用
$small dfs$

dfs计算的话只能过
$small 90$

90%数据，听了大佬的话，用一个数组将
$small 2e7$

2e7的数据记录下来，下次遇到直接输出就好了。

//优化 #pragma GCC optimize(2) //C #include<string.h> #include<stdio.h> #include<stdlib.h> #include<math.h> //C++ #include<unordered_map> #include<algorithm> #include<iostream> #include<istream> #include<iomanip> #include<climits> #include<cstdio> #include<string> #include<vector> #include<cmath> #include<queue> #include<stack> #include<map> #include<set> //宏定义 #define N 1010 #define DoIdo main //#define scanf scanf_s #define it set<ll>::iterator #define TT template<class T> //定义+命名空间 typedef long long ll; typedef unsigned long long ull; const ll mod = 1e9 + 7; const ll INF = 1e18; const int maxn = 2e7 + 10; using namespace std; //全局变量 int ans[maxn]; int mi = INT_MAX; //函数区 ll max(ll a, ll b) { return a > b ? a : b; } ll min(ll a, ll b) { return a < b ? a : b; } inline ll read() {  ll c = getchar(), Nig = 1, x = 0; while (!isdigit(c) && c != '-')c = getchar(); if (c == '-')Nig = -1, c = getchar(); while (isdigit(c))x = ((x << 1) + (x << 3)) + (c ^ '0'), c = getchar(); return Nig * x; } inline void dfs(int now, int cnt) { //当我的数减到0时记录最小值并跳出循环 if (now == 0) { if (mi > cnt) mi = cnt; return; } //枚举所有可能的系数 for (int i = 2; i <= 9; i++) { //只有i是now - 1的因子时才可能有解 if ((now - 1) % i == 0) { dfs((now - 1) / i, cnt + 1); } } } #define read read() //主函数 int DoIdo() {   ios::sync_with_stdio(false);  cin.tie(NULL), cout.tie(NULL); int S = read; int T = read; while (T--) { int x = read; //如果之前有过询问，直接判断数组的值就好 if (x <= 2e7 && ans[x] != 0) { if (ans[x] == INT_MAX) printf("Orz Brother Jien!n"); else printf("%dn", ans[x]); //千万别忘记跳过此次询问 continue; } //如果x不是S的因子，肯定无解 if (S % x) { printf("Orz Brother Jien!n"); //对于小于2e7的数据，记录到数组里 if (x <= 2e7) ans[x] = INT_MAX; } else {    mi = INT_MAX; //进行dfs判断是否有解，传入参数要除以x dfs(S / x, 0); //对于小于2e7的数据，记录到数组里 if (x <= 2e7) ans[x] = mi; //对于没有更新mi直接输出无解就好 if (mi != INT_MAX) printf("%dn", mi); else printf("Orz Brother Jien!n"); } } return 0; } //分割线---------------------------------QWQ /*   */