Been trying to solve FIBOFUN. All of my test cases work, however I keep getting WA? Can anyone help me?
Here is my code:
#include <iostream>
void multiply(unsigned long long F[2][2], unsigned long long B[2][2], unsigned long long m);
void power(unsigned long long F[2][2], unsigned long long n, unsigned long long m);
using namespace std;
unsigned long long fib(unsigned long long n, unsigned long long a, unsigned long long b,unsigned long long m)
{
unsigned long long F[2][2]={{1,1},{1,0}};
power(F,n,m);
return ((F[0][0]*(b%m)) + (F[0][1]*(a%m)));
}
void power(unsigned long long F[2][2],unsigned long long n,unsigned long long m)
{
if(n==1)
return;
unsigned long long B[2][2] = {{1,1},{1,0}};
power(F, n/2, m);
multiply(F, F, m);
if( n%2 != 0 )
multiply(F, B, m);
}
void multiply(unsigned long long F[2][2],unsigned long long B[2][2],unsigned long long m)
{
unsigned long long x = F[0][0] * B[0][0] + F[0][1] * B[1][0];
unsigned long long y = F[0][0] * B[0][1] + F[0][1] * B[1][1];
unsigned long long z = F[1][0] * B[0][0] + F[1][1] * B[1][0];
unsigned long long w = F[1][0] * B[0][1] + F[1][1] * B[1][1];
F[0][0] = x%m;
F[0][1] = y%m;
F[1][0] = z%m;
F[1][1] = w%m;
}
int main()
{
int t;
unsigned long long sum, a,b,n,m;
cin>>t;
for(int i = 0; i < t; i++)
{
cin>>a>>b>>n>>m;
if(m==0||n==0)
cout<<0;
sum = fib(n,a,b,m)-b;
cout<<sum%m;
}
return 0;
}