1 files changed, 45 insertions, 27 deletions
diff --git a/PlaygroundCpp/Sources/Playground.cpp b/PlaygroundCpp/Sources/Playground.cpp
index 2986140..2bbbeb9 100644
--- a/PlaygroundCpp/Sources/Playground.cpp
+++ b/PlaygroundCpp/Sources/Playground.cpp
@@ -1,38 +1,56 @@
 #include <iostream>
 //#include <gtest/gtest.h>
 
-static int getGCD(int a, int b) {
-	if (b == 0) {
-		return a;
-	}
+const int FIB_PISANO_PERIOD_FOR_TEN = 60;
 
-	if (b > a) {
-		return getGCD(b, a);
-	} else {
-		return getGCD(b, a % b);
+static int getFibNModM(long n) {
+	long r = n % FIB_PISANO_PERIOD_FOR_TEN;
+	if (r == 0)
+		return 0;
+	int firstN = 0;
+	int secondN = 1;
+	int tempHolder = 1;
+	for (int i = 1; i < r; i++) {
+		tempHolder = (firstN + secondN) % 10;
+		firstN = secondN;
+		secondN = tempHolder;
 	}
+	return secondN;
 }
-static long getLCM(int a, int b) {
-	// https://www.idomaths.com/hcflcm.php#formula
-	return (long) a * (long) b / (long) getGCD(a, b);
+static int getLastDigit(long n) {
+	if (n <= 1)
+		return (int) n;
+	int result = getFibNModM(n + 2);
+	if (result == 0)
+		return 9;
+	else
+		return result - 1;
 }
-
-//TEST(LCMTest, Zero) {
-//	ASSERT_EQ(getLCM(6, 8), 24);
-//}
-//
-//TEST(LCMTest, One) {
-//	ASSERT_EQ(getLCM(28851538, 1183019), 1933053046);
-//}
-//
-//TEST(LCMTest, Two) {
-//	ASSERT_EQ(getLCM(14159572, 63967072), 226436590403296);
-//}
+static int getLastDigit(long m, long n) {
+	if (m == n)
+		return getFibNModM(n);
+	else {
+		int sumFn = getLastDigit(n);
+		int sumFm;
+		if (m <= 1)
+			sumFm = 0;
+		else
+			sumFm = getLastDigit(m - 1);
+		if (sumFn >= sumFm)
+			return sumFn - sumFm;
+		else
+			return sumFn - sumFm + 10;
+	}
+}
+//TEST(FibPartialSumLastDigit, Ten_200) {
+//	ASSERT_EQ(getLastDigit(10, 200), 2);
+//TEST(FibPartialSumLastDigit, One_2) {
+//	ASSERT_EQ(getLastDigit(1, 2), 2);
 
 int main() {
-	int a, b;
-	std::cin >> a;
-	std::cin >> b;
-	long c = getLCM(a, b);
+	long m, n;
+	std::cin >> m;
+	std::cin >> n;
+	int c = getLastDigit(m, n);
 	std::cout << c << '\n';
 }