diff options
Diffstat (limited to 'PlaygroundCpp/Sources')
| -rw-r--r-- | PlaygroundCpp/Sources/Playground.cpp | 67 |
1 files changed, 51 insertions, 16 deletions
diff --git a/PlaygroundCpp/Sources/Playground.cpp b/PlaygroundCpp/Sources/Playground.cpp index caa008b..35ce7da 100644 --- a/PlaygroundCpp/Sources/Playground.cpp +++ b/PlaygroundCpp/Sources/Playground.cpp @@ -1,29 +1,63 @@ #include <iostream> //#include <gtest/gtest.h> -static int getGCD(int a, int b) { - if (b == 0) { - return a; - } +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; - if (b > a) { - return getGCD(b, a); - } else { - return getGCD(b, a % b); + 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(getGCD(18, 35), 1); +// ASSERT_EQ(getFibNModM(2015, 3), 1); //} // //TEST(FibLastDigitTest, One) { -// ASSERT_EQ(17657, getGCD(28851538, 1183019)); +// ASSERT_EQ(getFibNModM(239, 1000), 161); //} // //TEST(FibLastDigitTest, Three) { -// ASSERT_EQ(7, getGCD(1344, 217)); +// ASSERT_EQ(getFibNModM(2816213588, 30524), 10249); //} -// + //TEST(FibLastDigitTest, Forty) { // ASSERT_EQ(1344, getGCD(1344, 1344)); //} @@ -37,9 +71,10 @@ static int getGCD(int a, int b) { //} int main() { - int a, b; - std::cin >> a; - std::cin >> b; - int c = getGCD(a, b); + long n; + int m; + std::cin >> n; + std::cin >> m; + int c = getFibNModM(n, m); std::cout << c << '\n'; } |