正解（A* 或 IDA*）

这道题很像 dp，但不能用 dp 去做。原因第一是这题用 dp 空间复杂度过高（$P ^ 2$），第二是这题 dp 转移时循环顺序不好定。所以舍去 dp 做法。

现在这道题只能用搜索做了。dfs 肯定不行，迭代加深 或 bfs 时间会爆。所以这道题我们要用 A* 或 IDA* 来做。

估价函数很好定，大约是 $\log {\frac {P} {\max \{ x, y \}}}$ （令第一个工作变量与第二个工作变量分别为 $x, y$）。估价函数：(lg 是我预处理出的一个数组，值为 $\lfloor \log x \rfloor$，特别地，$lg_0 = 0$）

int val (int x, int y)
{
    return lg[n / x] + !(y == n || x << lg[n / x] == n); // 其中 n 是 P
}

我们设 $x$ 是 $x, y$ 中较大的数，那么由它操作所得来的 $x, y$ 有以下几种：

• $(x + y, y)$

• $(x - y, y)$

• $(2x, y)$

• $(2y, y)$

• $(x, x + y)$

• $(x, x - y)$

• $(x, 2y)$

• $(x, 2x)$

还有一个剪枝：如果 $gcd (x, y) \vert P$ 不成立，那么它们无论怎么操作依然都是 $gcd (x, y)$ 的倍数，不可能为 $p$ 。所以如果 $gcd (x, y) \vert P$ 不成立，立马减掉。

#include<bits/stdc++.h>
const int M = 40005;
const int K = 4;
using namespace std;

const int dx[K] = {1, 1, 2, 0}, dy[K] = {1, -1, 0, 2}; // 操作后 x 或 y 的值会等于 x * dx[i] + y * dy[i]

struct node
{
    int x, y, d, f;
    friend bool operator < (node x, node y)
    {
        return x.d + x.f > y.d + y.f;
    }
}   __node__;

node mn (int x, int y, int d, int f)
{
    __node__.x = x, __node__.y = y, __node__.d = d, __node__.f = f;
    return __node__;
}

int n, x, y, d, nx, ny, lg[M];
set <pair <int, int> > v; // 状态判重
priority_queue <node> q; // 优先队列

int gcd (int x, int y) // 最大公因数
{
    return y ? gcd (y, x % y) : x;
}

int val (int x, int y) // 估价函数
{
    return lg[n / x] + !(y == n || x << lg[n / x] == n);
}

int A_star () // A*
{
    q.push (mn (1, 0, 0, val (1, 0))), v.insert (make_pair (0, 0));
    while (!q.empty ())
    {
        x = q.top ().x, y = q.top ().y, d = q.top ().d, q.pop ();
        if (x == n || y == n)
        {
            return d;
        }
        if (v.find (make_pair (x, y)) != v.end ())
        {
            continue;
        }
        v.insert (make_pair (nx, ny));
        for (int i = 0; i < 4; i ++)
        {
            nx = x * dx[i] + y * dy[i], ny = y;
            if (nx < ny)
            {
                swap (nx, ny);
            }
            if (!nx || nx > n << 1 || ny && n % gcd (nx, ny))
            {
                continue;
            }
            q.push (mn (nx, ny, d + 1, val (nx, ny)));
        }
        for (int i = 0; i < 4; i ++)
        {
            nx = x, ny = x * dx[i] + y * dy[i];
            if (nx < ny)
            {
                swap (nx, ny);
            }
            if (!nx || nx > n << 1 || ny && n % gcd (nx, ny))
            {
                continue;
            }
            q.push (mn (nx, ny, d + 1, val (nx, ny)));
        }
    }
    return -1; // 其实这句没啥用，可以删掉。
}

void init () // 预处理
{
    lg[0] = 0;
    for (int i = 1; i <= n << 1; i ++)
    {
        lg[i] = lg[i - 1] + (i >> lg[i - 1] + 1);
    }
    return ;
}

int main ()
{
    cin >> n, init (), cout << A_star ();
    return 0;
}