Algorithm
problem Link : https://onlinejudge.org/index.php?option=onlinejudge&Itemid=8&page=show_problem&problem=1630
Let’s define another number sequence, given by the following function: f(0) = a f(1) = b f(n) = f(n − 1) + f(n − 2), n > 1 When a = 0 and b = 1, this sequence gives the Fibonacci Sequence. Changing the values of a and b, you can get many different sequences. Given the values of a, b, you have to find the last m digits of f(n). Input The first line gives the number of test cases, which is less than 10001. Each test case consists of a single line containing the integers a b n m. The values of a and b range in [0, 100], value of n ranges in [0, 1000000000] and value of m ranges in [1, 4]. Output For each test case, print the last m digits of f(n). However, you should NOT print any leading zero.
Sample Input 4 0 1 11 3 0 1 42 4 0 1 22 4 0 1 21 4
Sample Output 89 4296 7711 946
Code Examples
#1 Code Example with C Programming
Code -
C Programming
#include <bits/stdc++.h>
using namespace std;
// Pisano Period: the last 1,2,3,4 digits of fibonacci seq
// repeats with a period of 60/300/1500/15000
vector<int> period = {60,300,1500,15000};
vector<int> mod = {10,100,1000,10000};
int main()
{
int t,a,b,n,m;
scanf("%d",&t);
while(t--){
scanf("%d %d %d %d",&a,&b,&n,&m);
// generate seq up to period
n %= period[m-1];
vector<int> fib;
fib.push_back(a % mod[m-1]), fib.push_back(b % mod[m-1]);
for(int i=2;i < =n;i++)
fib.push_back((fib[i-1]+fib[i-2]) % mod[m-1]);
printf("%d\n",fib[n]);
}
}
Input
0 1 11 3
0 1 42 4
0 1 22 4
0 1 21 4
Output
4296
7711
946
Demonstration
UVA Online Judge solution - 10689-Yet another Number Sequence - UVA Online Judge solution in C,C++,java