2 files changed, 77 insertions, 0 deletions
diff --git a/AlgoDesignAndTechniqueEdxPython/sources/fibagain.py b/AlgoDesignAndTechniqueEdxPython/sources/fibagain.py
new file mode 100644
index 0000000..2f2c839
--- /dev/null
+++ b/AlgoDesignAndTechniqueEdxPython/sources/fibagain.py
@@ -0,0 +1,44 @@
+# Uses python3
+import sys
+
+def getFib(n):
+    if (n <= 1):
+        return n
+    fibLst = [None] * (n + 1)
+    fibLst[0] = 0
+    fibLst[1] = 1
+    for j in range(2, n + 1):
+        fibLst[j] = fibLst[j - 1] + fibLst[j - 2]
+    return fibLst[n]
+
+
+def getPisanoPeriod(m):
+    period = 2
+    remainder1 = 1
+    remainder2 = 1
+    
+    for i in range(3, 6 * m + 1):
+        period = period + 1
+        if (remainder2 == 1) & (remainder1 + remainder2 == m):
+            break
+        else:
+            tempHolder = remainder1 + remainder2
+            remainder1 = remainder2
+            if tempHolder >= m:
+                remainder2 = tempHolder - m
+            else:
+                remainder2 = tempHolder
+                
+    return period
+
+
+def getFibNModM(n, m):
+    p = getPisanoPeriod(m)
+    return getFib(n % p) % m
+
+if __name__ == '__main__':
+    entryNumbers = sys.stdin.read()
+    tokens = entryNumbers.split()
+    n = int(tokens[0])
+    m = int(tokens[1])
+    print(getFibNModM(n, m))
+\ No newline at end of file
diff --git a/AlgoDesignAndTechniqueEdxPython/tests/fibagainTest.py b/AlgoDesignAndTechniqueEdxPython/tests/fibagainTest.py
new file mode 100644
index 0000000..edcc5ba
--- /dev/null
+++ b/AlgoDesignAndTechniqueEdxPython/tests/fibagainTest.py
@@ -0,0 +1,33 @@
+'''
+Created on Aug 23, 2018
+
+@author: haidong
+'''
+import unittest
+
+from sources.fibagain import getPisanoPeriod, getFibNModM
+
+class Test(unittest.TestCase):
+
+
+    def testPisanoPeriod73(self):
+        self.assertEqual(getPisanoPeriod(73), 148)
+
+    def testPisanoPeriod2(self):
+        self.assertEqual(getPisanoPeriod(2), 3)
+
+    def testPisanoPeriod98(self):
+        self.assertEqual(getPisanoPeriod(98), 336)
+    
+    def testFibNModM2015_3(self):
+        self.assertEqual(getFibNModM(2015, 3), 1)
+
+    def testFibNModM239_1000(self):
+        self.assertEqual(getFibNModM(239, 1000), 161)
+
+    def testFibNModM2816213588_30524(self):
+        self.assertEqual(getFibNModM(2816213588, 30524), 10249)
+
+if __name__ == "__main__":
+    #import sys;sys.argv = ['', 'Test.testName']
+    unittest.main()
+\ No newline at end of file