cf134b.md

提示 1： 从起点出发的可能步骤太多，但从终点出发，前一步是什么是完全确定的。

提示 2： 考虑对所有的 $i$ ，求得到 $(i,n)$ 的最小步数。

从 $(a,b)$ 出发的可能性至少有两种，而步数一多，可能性就大幅增加。

但如果考虑某一个 $(a,b)$ 前一个是什么，就只需把大的数减去小的数就行了，因为只有的那个数可能是最后一次操作的。

于是我们考虑从后往前推。

不妨设某一个时刻第一次出现 $n$ ，则此时另一个数一定小于 $n$ 。（否则 $n$ 一定前一轮就出现了）。

于是枚举另一个数 $i$ 。如果直接暴力枚举每一步，时间复杂度可能达到 $\mathcal{O}(n)$ ，因为 $(1,n)$ 就需要这么多步。

由于 $(x,y)$ 和 $(y,x)$ 需要的步数是一样的，因此我们直接不妨设二元组左边的数不超过右边的数。

有没有什么优化的空间呢？假设我们当前是 $(a,b)$ ，其中 $b\geq a$ ，则最近的若干步是 $(a,b)\to (a,b-a)\to (a,b-2a)\to\dots\to(a,b\bmod a)$ ，于是只需经过 $\lfloor b/a\rfloor$ 次，就可以使得二元组变为 $(b\bmod a,a)$ 。

上面的过程如果直接递归可能到达 $(0,1)$ 这一状态，此时只需撤回最后一步操作就是 $(1,1)$ 。

需要注意的是，有些对是无法达到的，因为这些对可能到达 $(0,x)$ ，其中 $x\gt 1$ ，此时撤回前一步到不了 $(1,1)$ ，直接忽略对应情况即可。

实际上，上述过程类似于求最大公因数，而两个数的最大公因数也始终不变，因此 $1=\mathrm{gcd}(1,1)=\mathrm{gcd}(a,b)$ ，于是只有开头互质的两个数才可能从 $(1,1)$ 变过去。

时间复杂度为 $\mathcal{O}(n\log n)$ ，因为对于每一个 $i$ 最多只需要 $\mathcal{O}(\log n)$ 次计算，因为整体的递归过程跟求最大公因数并无二致。

具体代码如下——

Python 做法如下——

def main():
    def f(x, y):
        if x == 0: return -1
        return y // x + f(y % x, x)

    n = II()
    print(min(f(i, n) for i in range(1, n + 1) if math.gcd(i, n) == 1))

C++ 做法如下——

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    auto f = [&] (auto &self, int x, int y) -> int {
        if (x == 0) return -1;
        return y / x + self(self, y % x, x);
    };

    int n;
    cin >> n;

    int ans = n;
    for (int i = 1; i <= n; i ++) {
        if (gcd(i, n) == 1) {
            ans = min(ans, f(f, i, n));
        }
    }
    cout << ans;

    return 0;
}