Algorithm
Problem link- https://www.spoj.com/problems/FIBOFUN/
FIBOFUN - Fun with Fibonacci Series
Fibonacci series is a series in which every element is sum of previous 2 elements.
first 2elements are 0,1 and the series goes like 0,1,1,2,3,5,8,13 ........
What if you were given 2 random numbers as the starting of the series and u follow the same rule as the fibonacci rule.
for eg. if you were given 2 and 2 .. the series would become
2 2 4 6 10 16 26 .........
Now ur task is Simple ...
You will be given 2 numbers a & b .. the first and second term of the series..
you need to calculate the sum of first n numbers of the series so formed..
Since the numbers can be big you need to print the result mod some number 'M' provided in the input.
Input
first line will have single number 't' - number of test cases.
each test case will have 4 numbers a,b,n & M
a- first number of the series
b- second number of the series
n- calculate the sum till n numbers
M- print the result mod M
Output
single number for each case - sum of n terms mod M
Example
Input: 2
2 2 10 21
1 3 10 21
Output: 13
4
Explanation - for first case series is 2 2 4 6 10 16 26 42 68 110 .. Sum is 286.. o/p = 286%21 = 13
NOTE -
Number of test cases <=100.
0 <= a,b,m <= 10^8
1 <= n <= 10^8
Code Examples
#1 Code Example with Python Programming
Code -
Python Programming
A, B, N, M = 0, 0, 0, 0
class matrix:
a = []
def __init__(self, default=None):
if default is not None:
self.a = default
else:
self.a = [[0, 0], [0, 0]]
def __mul__(self, other):
s = matrix()
for i in range(2):
for j in range(2):
for k in range(2):
s.a[i][j] += self.a[i][k] * other.a[k][j]
for i in range(2):
for j in range(2):
s.a[i][j] %= M
return s
def __pow__(self, power, modulo=None):
if power == 1:
return matrix([[1, 1], [1, 0]])
if power % 2 == 1:
return self * (self.__pow__(power - 1))
half = self.__pow__(power // 2)
return half * half
T = int(input())
for _ in range(T):
A, B, N, M = map(int, input().split())
mat = matrix([[1, 1], [1, 0]]) ** N
print((mat.a[0][0] * B + mat.a[0][1] * A - B + M) % M)Input
2 2 10 21
1 3 10 21
Output
4
Demonstration
SPOJ Solution-Fun with Fibonacci Series-Solution in C, C++, Java, Python