summaryrefslogtreecommitdiff
path: root/PlaygroundCpp
diff options
context:
space:
mode:
authorHaidong Ji2018-08-19 10:48:24 -0500
committerHaidong Ji2018-08-19 10:48:24 -0500
commit1b625dab2d7b56e6b8d3289a0726724b3830e6b7 (patch)
treed2cb80502a4fc303c91d642a667959a44d1bc687 /PlaygroundCpp
parent5ac928038c567f70884d21d363fd862647d373bd (diff)
GCD done!
Diffstat (limited to 'PlaygroundCpp')
-rw-r--r--PlaygroundCpp/Sources/Playground.cpp62
1 files changed, 24 insertions, 38 deletions
diff --git a/PlaygroundCpp/Sources/Playground.cpp b/PlaygroundCpp/Sources/Playground.cpp
index 8ef7faa..caa008b 100644
--- a/PlaygroundCpp/Sources/Playground.cpp
+++ b/PlaygroundCpp/Sources/Playground.cpp
@@ -1,59 +1,45 @@
#include <iostream>
//#include <gtest/gtest.h>
-//int get_fibonacci_last_digit_naive(int n) {
-// if (n <= 1)
-// return n;
-//
-// int previous = 0;
-// int current = 1;
-//
-// for (int i = 0; i < n - 1; ++i) {
-// int tmp_previous = previous;
-// previous = current;
-// current = tmp_previous + current;
-// }
-//
-// return current % 10;
-//}
+static int getGCD(int a, int b) {
+ if (b == 0) {
+ return a;
+ }
-int get_fibonacci_last_digit_optimized(int n) {
- if (n <= 1)
- return n;
- int fibLastDigitArray[n];
- fibLastDigitArray[0] = 0;
- fibLastDigitArray[1] = 1;
- for (int i = 2; i < n + 1; i++) {
- fibLastDigitArray[i] = (fibLastDigitArray[i - 1]
- + fibLastDigitArray[i - 2]) % 10;
+ if (b > a) {
+ return getGCD(b, a);
+ } else {
+ return getGCD(b, a % b);
}
- return fibLastDigitArray[n];
}
-
//TEST(FibLastDigitTest, Zero) {
-// ASSERT_EQ(get_fibonacci_last_digit_naive(0), 0);
+// ASSERT_EQ(getGCD(18, 35), 1);
//}
//
//TEST(FibLastDigitTest, One) {
-// ASSERT_EQ(get_fibonacci_last_digit_naive(1), 1);
+// ASSERT_EQ(17657, getGCD(28851538, 1183019));
//}
//
//TEST(FibLastDigitTest, Three) {
-// ASSERT_EQ(get_fibonacci_last_digit_naive(3), 2);
+// ASSERT_EQ(7, getGCD(1344, 217));
//}
//
//TEST(FibLastDigitTest, Forty) {
-// ASSERT_EQ(get_fibonacci_last_digit_naive(40), 5);
-// ASSERT_EQ(get_fibonacci_last_digit_optimized(40), 5);
+// ASSERT_EQ(1344, getGCD(1344, 1344));
//}
//
//TEST(FibLastDigitTest, ThreeThreeOne) {
-// ASSERT_EQ(get_fibonacci_last_digit_optimized(331), 9);
-// ASSERT_EQ(get_fibonacci_last_digit_optimized(327305), 5);
+// ASSERT_EQ(4, getGCD(14159572, 63967072));
+//}
+//
+//TEST(FibLastDigitTest, ReverseAB) {
+// ASSERT_EQ(4, getGCD(14159572, 63967072));
//}
+
int main() {
- int n;
- std::cin >> n;
- int c = get_fibonacci_last_digit_optimized(n);
- std::cout << c << '\n';
- }
+ int a, b;
+ std::cin >> a;
+ std::cin >> b;
+ int c = getGCD(a, b);
+ std::cout << c << '\n';
+}