当前位置：首页 > news >正文

Luogu P2090 [CF134B] 数字对

news 2026/6/11 10:39:02

Luogu 题目传送门
双倍经验（原题）

洛谷打完卡(运势 § 大吉 § ) 后，随机题目跳转到了这一题

\(\;\)

题目大意

~~没什么好说的~~，我就直接 Copy + Paste
让我们假设有一对数 (a, b) 。我们可以从前一步得到后一对数 (a + b, b) 或者 (a, a + b)。

让我们规定一开始这对数为 (1,1) 。你的任务就是找到数k，使k为从 (1,1) 转换到一对至少含有一个 \(n\) 的数对的最少步骤。

输入样例：

5

输出为:

3

\(\;\)

算法!

我们要试图从 (1,1) 转换到 (n,k), \(k\) 是任意数字，\(n\) 是我们需要的数字。发现我们可以用 bfs 暴力搜索，每一次转换到 (a, a+b) 和 (a+b, a)。代码如下：

#include <bits/stdc++.h>
using namespace std;
#define int long long
int n,ans=0x7FFFFFFFFFFFFFFF;void bfs(int a,int b,int steps) {if (a>nor  b>n) return void();if (a==n||b==n) return ans=min(ans,steps),void();=bfs(a,a+b,num,steps+1);bfs(a+b,a,num,steps+1);
}signed main() {cin>>n;bfs(1,1,0);cout<<ans;return 0;
}

时间复杂度：O(N^2)

结果 TLE 了，值得了 60 分。
\(\;\)

我们换一个思路，发现我们最终要到 n, k。反过来也会一样，从 n, k 一直转换到 1, 1。我们取 \(k\) 从 \(1 \sim n-1\)，代码如下

#include <bits/stdc++.h>
using namespace std;
#define int long long
int n,ans=0x7FFFFFFFFFFFFFFF;
void bfs(int a,int b,int steps) {if (a<=0 or b<=0) return void();if (a==1 and b==1) return ans=min(ans,steps),void();if (b>a) bfs(b-a,a,steps+1);else bfs(a-b,b,steps+1);
}signed main() {cin>>n;for (int i=1;i<n;i++) dfs(i,n,0);cout<<ans;return 0;
}

\(\;\)

时间复杂度：O(N log N)

空间复杂度：O(log N)

现在已经 AC了，但是我们可以更快。
发现当我们知道了尾端 (n, k)，只有一条或没有路到 (1, 1)。所以我们可以更改 bfs 的算法成模拟算法：

while (a!=1 || b!=1) {if (a<=0 || b<=0) return -1;if (b>a) b=b-a;else a=a-b;
}
return steps;

再仔细检查，我们可以二次加速 --> 当算的时候 steps 已经超过了 ans，我们就直接返回，不搜了。由此我们可以得到史上最短，最快的代码：

时间复杂度：O(N log N)

空间复杂度：O(1)

完整代码

#include <bits/stdc++.h>
using namespace std;
#define int long long
int n,ans=0x7FFFFFFFFFFFFFFF,tmp;
int bfs(int a,int b,int steps) {while (a!=1 || b!=1) {if (a<=0 || b<=0) return -1;if (b>a) b=b-a;else a=a-b;if (++steps>=ans) return steps+1;}return steps;
}
signed main() {cin>>n;if (n==1) {write(0);return 0;}for (int i=n;i>=1;i--) {tmp=bfs(i,n,0);if (tmp==-1) continue;ans=min(ans,tmp);}cout<<ans;return 0;
}

\(\;\)