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
#include <cstdio>
#include <cstring>

int main() 
{
	char cstr[19];
	scanf("%s", cstr);
	long long mod = 1;
	long long cval = 0;
	for(char* c = cstr; *c >= '0' && *c <= '9'; ++c) {
		mod *= 10;
		cval *= 10;
		cval += (*c)-'0';
	}

	if (mod < 1000) {
		mod = 1000;
	}

	bool done = false;
	long long F0 = 0;
	long long F1 = 1;
	long long F2;
	long long limit = mod + mod/2;

	long long modSm = 1000;

	if (F0 != cval && F1 != cval) {
		for (long long i = 2; i < limit; ++i) {
			F2 = (F0 + F1) % mod;
			if (F2 == cval) {
				printf("%lld\n", i + ((i > 100) ? 0 : limit));
				done = true;
				break;
			}

			while (F2 % modSm == cval % modSm) {
				modSm *= 10;
			}

			if (i >= (3*modSm/2)) {
				break;
			}

			F0 = F1;
			F1 = F2;
		}

		if (!done) {
			printf("NIE\n");
		}
	} else {
		printf("%lld\n", limit + ((F0 == cval) ? 0 : 1));
	}

	return 0;
}