自动搬运

查看原文

来自洛谷，原作者为

	wangbinfeng 今天搞完大概就永远不会碰 OI 了，大家祝好！

搬运于2025-08-24 22:58:32，当前版本为作者最后更新于2024-08-08 08:55:43，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

已被打回两次，烦请告知具体不合规的位置，以便作者进行修改。

• 题解意义：这道题的原题空间限制是 30000KiB，所以必须用 ID-DFS。但是 luogu 里这道题的空间限制是 512.00MiB，所以用 BFS 的空间复杂度是没有问题的。鉴于这道题可以被作为是 ID-DFS 的模板题，建议还是跟着其他题解学一下 ID-DFS。那么为什么会有这个题解呢？因为我为了验证 BFS 可以通过本题，尝试了长达 $20$ 天，所以本题解分享方法，以免后来人重复浪费时间。
• 题意简述：有两个变量，其初值分别为 $x$ 和 $1$，请问这两个变量最少经过多少次乘或除操作，使得至少一个变量的值成为 $x^P$。
• 必备公式：$x^a\times x^b=x^{a+b},\frac{x^a}{x^b}=x^{a-b},x^0=1$。

首先可以发现变量 $x$ 其实没啥用，因为乘除操作完全可以转换为对其指数加减操作，所以题目可以转化为两个数 $0,1$ 经过任意多操作得到 $P$。因为 $P\le2\times 10^4$，所以搜索即可。 对于状态 $(x,y)$，可以转移到 $ \begin{cases} (x,x+x)\\(x,y+y)\\(x+x,y)\\(y+y,y)\\(x,x+y)\\(x+y,y)\\(x,\lvert x-y\rvert)\\(\lvert x-y\rvert,y) \end{cases}$ 共计 $8$ 种状态，搜索一下。

设答案为 $ans$，则时间复杂度约为 $8^{ans}$，经测试 $ans\le20$，跑所有状态显然不可能完成。容易想到记忆化，不幸的是还是超时。

考虑到令 $A=\gcd(x,y)$，则 $x=\lambda_1A,y=\lambda_2 A$，那么他们凑出来的数将一定也只能是 $A$ 的倍数（也可以把 $\lambda$ 搞成零然后再找，但显然更劣）。那么如果发现若 $P\bmod\gcd(x,y)\neq0$，那么就可以直接剪枝。

现在 ID-DFS 已经可以 $\colorbox{green}{\color{white}{AC}}$ 了，但是 BFS 还是有可能会 $\colorbox{black}{\color{white}{TLE}}$，考虑继续卡常。由于每个人卡常的方法不尽相同，这里仅介绍我本人的卡常方法：

1. 手写队列，不要用 STL 的 queue，经测试可以节省 300 ms。
2. 手写 gcd，不要用 STL 的 __gcd。
3. 用 bitset 或 bool 数组，不要用 STL 的 map/unordered_map。

总结一下就是少用或不用 STL。

代码如下：

#include <bits/stdc++.h>
using namespace std;
int p, cnt;
const int maxp = 2e4 + 9;
bitset<maxp * maxp * 5> vis;
const int M = 4e7 + 5, P = 4e7;
struct Node
{
    unsigned short x, y, dep;
} v[M];

int l = 1, r = 0;
#define min(a, b) (a < b ? a : b)
#define max(a, b) (a > b ? a : b)
#define ctz __builtin_ctz
int az, bz, z, t;
inline int gcd(int a, int b)
{
    if (!a || !b)
        return 0;
    az = ctz(a), bz = ctz(b), z = (az > bz) ? bz : az, t;
    b >>= bz;
    while (a)
        a >>= az, t = a - b, az = ctz(t), b = min(a, b), a = t < 0 ? -t : t;
    return b << z;
}
int x, y, dep;
inline int bfs()
{
    Node now = {1, 0, 0};
    for (v[++r] = now, (r == P) && (r = 0); 1; l++, (l == P + 1) && (l = 1))
    {
        cnt++;
        x = max(v[l].x, v[l].y), y = min(v[l].x, v[l].y), dep = v[l].dep;
        if (x == p || y == p)
        {
            cout << dep;
            return dep;
        }
        if (x > p * 2)
            continue;
        if (vis[x * p * 2 + y])
            continue;
        if (gcd(x, y) && p % gcd(x, y))
            continue;
        vis[x * p * 2 + y] = true;
        now.x = x * 2, now.y = y, now.dep = dep + 1, v[++r] = now, (r == P) && (r = 0);
        now.x = x * 2, now.y = x, now.dep = dep + 1, v[++r] = now, (r == P) && (r = 0);
        now.x = x, now.y = y * 2, now.dep = dep + 1, v[++r] = now, (r == P) && (r = 0);
        now.x = y, now.y = y * 2, now.dep = dep + 1, v[++r] = now, (r == P) && (r = 0);
        now.x = x + y, now.y = x, now.dep = dep + 1, v[++r] = now, (r == P) && (r = 0);
        now.x = x + y, now.y = y, now.dep = dep + 1, v[++r] = now, (r == P) && (r = 0);
        now.x = x - y, now.y = x, now.dep = dep + 1, v[++r] = now, (r == P) && (r = 0);
        now.x = x - y, now.y = y, now.dep = dep + 1, v[++r] = now, (r == P) && (r = 0);
    }
}
signed main()
{
    ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
    cin >> p;
    bfs();
}

• 后记： 经过我本人的测试，其实 ID-DFS 和 BFS 的遍历节点数相近，为同一个数量级，且 BFS 遍历的节点数甚至会更小（UPD：经过第二次测试，发现结果与第一次测试结论不符，等待最终确定结果），不清楚为什么经过卡常的 BFS 算法会比 ID-DFS 慢了 $\frac{835ms}{18ms}\approx46.3$ 倍（对于第 #11 个测试点），希望有大佬可以告知原因。
• 鸣谢：感谢 @C20252323tzy 帮我卡常，题解中的代码也是这位大佬修改的，在此表示万分的感谢。
• 附录：关于代码运行时间的测试（在这个链接进行测试，仅供参考）：