1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
#include "stdio.h"
#include <map>

long long cykl[20];
long long offsetCnt[20];
long long offset[20][50000];

std::map<long long, long long> Fmap;

long long sqrMod(long long a)
{
	long long a1 = a / 1000000000;
	long long a0 = a % 1000000000;

	long long res = (((2 * a1 * a0) % 1000000000LL) * 1000000000LL + a0 * a0) % (1000000000LL*1000000000LL);
	return res;
}

long long FIB(long long n)
{
	if (n == 0) { return 0; }
	if (n == 1) { return 1; }
	if (n == 2) { return 1; }

	std::map<long long, long long>::iterator it = Fmap.find(n);
	if (it != Fmap.end())
	{
		return it->second;
	}

	if ((n & 1) == 1)
	{
		long long f1 = FIB((n + 1) / 2); 
		long long f2 = FIB((n - 1) / 2);
		long long res = (sqrMod(f1) + sqrMod(f2)) % (1000000000LL*1000000000LL);
		Fmap[n] = res;
		return res;
	}
	else
	{
		long long f1 = FIB((n / 2) + 1); 
		long long f2 = FIB((n / 2) - 1);
		long long res = (sqrMod(f1) - sqrMod(f2) + (1000000000LL*1000000000LL)) % (1000000000LL*1000000000LL);
		Fmap[n] = res;
		return res;
	}
}

int main()
{
	char str[100];

	scanf("%s", str);

	int dig = 0;
	while (str[dig] != 0) { dig++; }

//	printf("FIB:%lld\n", FIB(45LL));

/*	for (int i = 0; i < 1000; i++)
	{
		printf("%i:%lld\n", i, FIB(i));
	}
*/

	cykl[0] = 1;
	offsetCnt[0] = 1;
	offset[0][0] = 0;

	long long mask = 1;
	int d = 1;
	while (d <= dig)
	{
		mask *= 10;
		long long i = cykl[d - 1];
		while ((FIB(i) % mask) != 0 || (FIB(i + 1) % mask) != 1)
		{
			i += cykl[d - 1];
		}

		cykl[d] = i;
		//printf("CYKL:%i %lld\n", d, cykl[d]);
		d++;
	}

	mask = 1;
	d = 1;
	long long val = 0;
	while (d <= dig)
	{
		offsetCnt[d] = 0;
		val += mask * (str[dig - d] - '0');
		mask *= 10;
		long long p = 0;
		while (p < cykl[d])
		{
			for (int i = 0; i < offsetCnt[d - 1]; i++)
			{
				if ((FIB(p + offset[d - 1][i]) % mask) == val)
				{
					offset[d][offsetCnt[d]] = p + offset[d - 1][i];
					offsetCnt[d]++;
				}
			}
			p += cykl[d - 1];
		}
		d++;
	}

	if (offsetCnt[dig] > 0)
	{
		printf("%lld\n", offset[dig][offsetCnt[dig] - 1]);
		//printf("%s %lld -> %lld\n", str, offset[dig][offsetCnt[dig] - 1], FIB(offset[dig][offsetCnt[dig] - 1]));
	}
	else
	{
		printf("NIE\n");
	}

	return 0;
}