From 0cb94b3d22347b099b19cbf9bdfd4179d3a5c148 Mon Sep 17 00:00:00 2001
From: Haidong Ji
Date: Thu, 23 Aug 2018 19:48:29 -0500
Subject: Done!

I actually started implementing this in Java first, but ran into long
int overflow issues. Decided to get it working in Python first. I'm glad
it worked! Now back to implement it in Java!---
 .../sources/fibagain.py                            | 44 ++++++++++++++++++++++
 1 file changed, 44 insertions(+)
 create mode 100644 AlgoDesignAndTechniqueEdxPython/sources/fibagain.py

(limited to 'AlgoDesignAndTechniqueEdxPython/sources')

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
-- 
cgit v1.2.3