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
|
#include <iostream>
//#include <gtest/gtest.h>
static int getPisanoPeriodOptimized(int m) {
// this optimized algorithm is obtained through the
// discussion starting around 7:30 mark of the following
// video. We know the upper bound for the loop, which
// is 6*m, through articles listed above
// https://www.youtube.com/watch?v=Nu-lW-Ifyec
// https://en.wikipedia.org/wiki/Pisano_period
// The unoptimized naive algorithm looks for modulus
// 0 followed by 1
int period = 2;
int remainder1 = 1;
int remainder2 = 1;
for (int i = 3; i <= 6 * m; i++) {
period++;
if (remainder2 == 1 && (remainder1 + remainder2 == m)) {
break;
} else {
int tempHolder = remainder1 + remainder2;
remainder1 = remainder2;
if (tempHolder >= m) {
remainder2 = tempHolder - m;
} else {
remainder2 = tempHolder;
}
}
}
return period;
}
static int getFibNModM(long n, int m) {
int p = getPisanoPeriodOptimized(m);
long r = n % p;
if (r == 0)
return 0;
int firstN = 0;
int secondN = 1;
int tempHolder = 1;
for (int i = 1; i < r; i++) {
tempHolder = (firstN + secondN) % m;
firstN = secondN;
secondN = tempHolder;
}
return secondN;
}
//TEST(FibLastDigitTest, Zero) {
// ASSERT_EQ(getFibNModM(2015, 3), 1);
//}
//
//TEST(FibLastDigitTest, One) {
// ASSERT_EQ(getFibNModM(239, 1000), 161);
//}
//
//TEST(FibLastDigitTest, Three) {
// ASSERT_EQ(getFibNModM(2816213588, 30524), 10249);
//}
//TEST(FibLastDigitTest, Forty) {
// ASSERT_EQ(1344, getGCD(1344, 1344));
//}
//
//TEST(FibLastDigitTest, ThreeThreeOne) {
// ASSERT_EQ(4, getGCD(14159572, 63967072));
//}
//
//TEST(FibLastDigitTest, ReverseAB) {
// ASSERT_EQ(4, getGCD(14159572, 63967072));
//}
int main() {
long n;
int m;
std::cin >> n;
std::cin >> m;
int c = getFibNModM(n, m);
std::cout << c << '\n';
}
|
