Hướng dẫn giải của [200 đề thầy Đức] Bài 112: Kiểm tra số Fibonacci
Chỉ dùng lời giải này khi không có ý tưởng, và đừng copy-paste code từ lời giải này. Hãy tôn trọng người ra đề và người viết lời giải.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
Hướng dẫn giải
Sinh dãy Fibonacci cho tới khi vượt 2 × 10^9 (chỉ khoảng 46 số), rồi tìm vị trí đầu tiên có giá trị n. Lưu ý F(1) = F(2) = 1 nên số 1 ở vị trí 1.
Bài này chỉ cần sinh dãy và tìm kiếm, nên chỉ viết 1 sub (lời giải đầy đủ). Đạt 21/21 test.
Sub 1: Sinh dãy và tìm kiếm — ~O(\log n)~
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
// Sinh day Fibonacci den khi vuot 2 * 10^9 (chi khoang 46 so)
// f[0] = F(1) = 1, f[1] = F(2) = 1, ...
vector<long long> f = {1, 1};
while (f.back() <= 2000000000LL)
f.push_back(f[f.size() - 1] + f[f.size() - 2]);
int T;
cin >> T;
while (T--) {
long long n;
cin >> n;
int ans = -1;
// Tim vi tri dau tien trong day co gia tri n (n = 1 xuat hien o vi tri 1)
for (size_t i = 0; i < f.size(); i++)
if (f[i] == n) {
ans = (int)i + 1;
break;
}
cout << ans << "\n";
}
return 0;
}
Bình luận