You will be given two positive numbers M and N. Your task is to print the greatest common divisor of Fib(M) and Fib(N) where Fib(x) means the x'th Fibonacci numbers defined as:
Fib(0) = 0
Fib(1) = 1
for n > 1, Fib(n) = Fib(n-1) + Fib(n-2)
Example 1:
Input: M = 3, N = 6
Output: 2
Explanation: Fib(3) = 2 and Fib(6) = 8
So, GCD(2,8)%100 = 2
Ã¢â¬â¹Example 2:
Input: M = 7, N = 8
Output: 1
Explanation: Fib(7) = 13 and Fib(8) = 21
So, GCD(13,21)%100 = 1
Your Task:  
You don't need to read input or print anything. Your task is to complete the function fibGcd() which takes M and N as inputs and returns the answer.The answer may be very large, compute the answer modulo 100.
Expected Time Complexity: O(min(M, N))
Expected Auxiliary Space: O(1)
Constraints:
1 ≤ M, N ≤ 10^{3}

Source: geeksforgeeks | Difficulty: EASY
Tags: Mathematics

Starter code: #User function Template for python3

class Solution:
    def fibGcd (self, M, N):
        #complete the function here

Solutions:
class Solution:

	def gcd(self, a, b):
		r = a % b
		while r != 0:
			a = b
			b = r
			r = a % b
		return b

	def fib(self, n):
		if n == 0:
			return 0
		elif n == 1:
			return 1
		else:
			(a, b) = (0, 1)
			for i in range(n - 1):
				c = a + b
				a = b
				b = c
			return b

	def fibGcd(self, M, N):
		(x, y) = (self.fib(M), self.fib(N))
		return self.gcd(x, y) % 100


import math

class Solution:

	def fibGcd(self, M, N):
		(f1, f2) = (0, 1)
		f = [0, 1]
		for i in range(max(M, N)):
			f3 = f1 + f2
			f.append(f3)
			f1 = f2
			f2 = f3
		return math.gcd(f[M], f[N]) % 100


import sys
sys.setrecursionlimit(1100)

class Solution:

	def fibGcd(self, M, N):

		def gcd(a, b):
			if not b:
				return a
			return gcd(b, a % b)

		def fib(n):
			(a, b, c) = (1, 1, 2)
			if n < 3:
				return b
			while c < n:
				(a, b, c) = (b, a + b, c + 1)
				if c == n:
					return b
		return gcd(fib(M), fib(N)) % 100


class Solution:

	def fibGcd(self, M, N):
		from math import gcd
		F = [0, 1]
		mx = max(M, N)
		for i in range(2, mx + 1):
			F.append(F[i - 1] + F[i - 2])
		return gcd(F[M], F[N]) % 100


class Solution:

	def fibGcd(self, M, N):
		import math
		gcd_is = math.gcd(M, N)
		arr = [0] * (gcd_is + 1)
		arr[0] = 0
		arr[1] = 1
		i = 2
		while i <= gcd_is:
			arr[i] = (arr[i - 1] % 100 + arr[i - 2] % 100) % 100
			i += 1
		return arr[gcd_is] % 100


class Solution:

	def fibGcd(self, M, N):
		y = self.gcd(M, N)
		return self.fib(y) % 100

	def fib(self, N):
		dp = [0 for i in range(N + 1)]
		dp[0] = 0
		dp[1] = 1
		for i in range(2, N + 1):
			dp[i] = (dp[i - 1] % 100 + dp[i - 2] % 100) % 100
		return dp[N] % 100

	def gcd(self, a, b):
		if b == 0:
			return a
		return self.gcd(b, a % b)


import math

class Solution:

	def Fib_Last_Digit(self, n):
		arr = [0] * (n + 1)
		arr[0] = 0
		arr[1] = 1
		i = 2
		while i <= n:
			arr[i] = (arr[i - 1] % 100 + arr[i - 2] % 100) % 100
			i += 1
		return arr[n] % 100

	def fibGcd(self, M, N):
		c = math.gcd(M, N)
		return self.Fib_Last_Digit(c) % 100


import math

class Solution:

	def fibGcd(self, M, N):
		x = [0, 1]
		for i in range(2, M + N + 1):
			x.append(x[-1] + x[-2])
		l = x[M]
		k = x[N]
		return math.gcd(l, k) % 100


from math import *

class Solution:

	def fibGcd(self, M, N):
		l = []
		a = 1
		b = 1
		l.append(1)
		l.append(1)
		for i in range(max(M, N)):
			c = a + b
			l.append(c)
			a = b
			b = c
		return gcd(l[M - 1], l[N - 1]) % 100


import math

class Solution:

	def fibGcd(self, m, n):
		fib = [0, 1]
		for i in range(2, max(m, n) + 1):
			fib.append(fib[i - 1] + fib[i - 2])
		return math.gcd(fib[m], fib[n]) % 100


class Solution:

	def fibGcd(self, M, N):
		from math import gcd
		m = max(M, N) + 1
		fib = [0] * m
		fib[0] = 0
		fib[1] = 1
		for i in range(2, m):
			fib[i] = fib[i - 1] + fib[i - 2]
		return gcd(fib[M], fib[N]) % 100


from math import gcd

def fib(n):
	f = [0, 1]
	for i in range(2, n + 1):
		f[i % 2] = f[0] + f[1]
	return f[n % 2]

class Solution:

	def fibGcd(self, M, N):
		return gcd(fib(M), fib(N)) % 100


from math import gcd

class Solution:

	def fibGcd(self, M, N):
		s = []
		s.append(1)
		s.append(1)
		a = 0
		for i in range(2, max(M, N) + 1):
			a = s[i - 2] + s[i - 1]
			s.append(a)
		c = gcd(s[M - 1], s[N - 1])
		return c % 100


def gcd(a, b):
	if a == 0:
		return b
	if b == 0:
		return a
	return gcd(b, a % b)

class Solution:

	def fibGcd(self, M, N):
		n = gcd(M, N)
		i = 1
		j = 1
		for _ in range(2, n):
			(i, j) = (j, i + j)
		return j % 100