blob: b38f44afffbeb7f1134f9039127c7e2a566665db (
plain)
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
|
import java.util.Scanner;
public class FibAgain {
// public static BigInteger getFib(int n) {
// if (n <= 1)
// return BigInteger.valueOf(n);
// final BigInteger[] fibArray = new BigInteger[n + 1];
// fibArray[0] = BigInteger.valueOf(0);
// fibArray[1] = BigInteger.valueOf(1);
// for (int i = 2; i < n + 1; i++) {
// fibArray[i] = fibArray[i - 1].add(fibArray[i - 2]);
// }
// return fibArray[n];
// }
//
// public static BigInteger getFibOptimized(int n) {
// if (n <= 1)
// return BigInteger.valueOf(n);
// final BigInteger[] fibArray = new BigInteger[n + 1];
// BigInteger firstFib = BigInteger.valueOf(0);
// BigInteger secondFib = BigInteger.valueOf(1);
// BigInteger tempHolder = BigInteger.valueOf(0);
// for (int i = 2; i < n + 1; i++) {
// tempHolder = firstFib.add(secondFib);
// firstFib = secondFib;
// secondFib = tempHolder;
// }
// return secondFib;
// }
public 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;
}
public 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;
}
public static void main(String args[]) {
Scanner in = new Scanner(System.in);
long n = in.nextLong();
int m = in.nextInt();
System.out.println(getFibNModM(n, m));
}
}
|
