结论：斐波那契数列（\(F_1 = F_2 = 1, \forall i \ge 3, F_i = F_{i - 1} + F_{i - 2}\)）在 \(\forall i \ge 3, \bmod\ 10^i\) 意义下有循环节 \(1.5 \times 10^i\)。
考虑利用这个结论，先找出所有 \(i \le 1.5 \times 10^3, F_i \equiv n \pmod{10^3}\) 的 \(i\) 组成的集合 \(S\)。然后将模数由 \(10^k\) 推至 \(10^{k + 1}\)，同时计算出 \(i \le 1.5 \times 10^{k + 1}, F_i \equiv n \pmod{10^{k + 1}}\) 的 \(i\) 组成的新的集合 \(S\)。
对于原来在 \(S\) 中的一个元素 \(x\)，可能成为新的 \(S\) 中元素的有 \(x, 10^k + x, 2 \times 10^k + x, \ldots, 9 \times 10^k + x\)。于是只要计算出这些数的 \(F_x\) 即可。可以使用矩阵快速幂。
code
// Problem: E. Fibonacci Number
// Contest: Codeforces - Codeforces Round 122 (Div. 1)
// URL: https://codeforces.com/problemset/problem/193/E
// Memory Limit: 256 MB
// Time Limit: 3000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include <bits/stdc++.h>
#define pb emplace_back
#define fst first
#define scd second
#define mkp make_pair
#define mems(a, x) memset((a), (x), sizeof(a))
using namespace std;
typedef long long ll;
typedef double db;
typedef unsigned long long ull;
typedef long double ldb;
typedef pair<ll, ll> pii;
const int maxn = 1510;
ll n, mod = 1000, m = 1500, f[maxn];
inline ll qmul(ll x, ll y) {
x %= mod;
ll res = 0;
while (y) {
if (y & 1) {
res = (res + x) % mod;
}
x = (x + x) % mod;
y >>= 1;
}
return res;
}
struct mat {
ll a[2][2];
mat() {
mems(a, 0);
}
};
inline mat operator * (const mat &a, const mat &b) {
mat res;
for (int k = 0; k < 2; ++k) {
for (int i = 0; i < 2; ++i) {
for (int j = 0; j < 2; ++j) {
res.a[i][j] = (res.a[i][j] + qmul(a.a[i][k], b.a[k][j])) % mod;
}
}
}
return res;
}
inline mat qpow(mat a, ll p) {
mat res;
res.a[0][1] = 1;
while (p) {
if (p & 1) {
res = res * a;
}
a = a * a;
p >>= 1;
}
return res;
}
inline ll F(ll n) {
mat a;
a.a[0][1] = a.a[1][0] = a.a[1][1] = 1;
a = qpow(a, n);
return a.a[0][0];
}
void solve() {
scanf("%lld", &n);
if (!n) {
puts("0");
return;
}
f[1] = 1;
for (int i = 2; i <= m; ++i) {
f[i] = (f[i - 1] + f[i - 2]) % mod;
}
vector<ll> S;
for (int i = 1; i <= m; ++i) {
if (f[i] == n % mod) {
S.pb(i);
}
}
for (int _ = 0; _ < 10; ++_) {
mod *= 10;
m *= 10;
vector<ll> T;
for (ll x : S) {
for (ll y = x; y <= m; y += (m / 10)) {
if (F(y) == n % mod) {
T.pb(y);
}
}
}
S = T;
}
printf("%lld\n", S.empty() ? -1LL : *min_element(S.begin(), S.end()));
}
int main() {
int T = 1;
// scanf("%d", &T);
while (T--) {
solve();
}
return 0;
}