01-algorithmic_toolbox/01-intro/05-fibonacci_huge/fibonacci_huge.cpp


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

#include <iostream>

long long get_fibonaccihuge(long long n, long long m)
{
    long long a, b, c, i; //, r, g, R;
    long long g;

    // length of pisano period pi(m)
    a = 0; b = 1;
    g = 0;
    /* Fi mod m */
    for (i = 0; ; i++) {
        c = a + b;
        if (c >= m)
            c -= m;
        // start pattern is 011
        if (c == 0)
            g = ((g == 0) ? 1 : 0);
        else if (g == 1)
            g = ((c == 1) ? 2 : 0);
        else if (g == 2) {
            if (c == 1)
                break;
            g = 0;
        }
        /* if (g == 2) { */
        /*     i += 1; */
        /*     break; */
        /* } */

        a = b;
        b = c;
    }

    /* g = n % i; */
    g = (n / i);
    g = n - (g * i);

    if (g <= 1)
        return g;

    /* Fg mod m */
    a = 0; b = 1;
    for (i = 1; i < g; i++) {
        c = a + b;
        if (c >= m)
            c -= m;
        a = b;
        b = c;
    }

    return b;
}

int main() {
    long long n, m;
    std::cin >> n >> m;
    std::cout << get_fibonaccihuge(n, m) << '\n';
}