# HackerEarth Special series problem solution

In this HackerEarth Special series problem solution Consider a series F that is defined as follows:
1. F(1) = 1
2. F(2) = 1
3. F(3) = 2
4. For n >= 3, F(n*n) - F(n + 1) x F(n -1) = ((-1) to power n)
Given two integers n and m. We need to make the nth term and mth term of the series co-prime. Find the largest positive number by which we must divide the nth term and mth term of the series such both terms become co-prime. Since, this number can be very large, print it modulo 10 to power 9 plus 7.

## HackerEarth Special series problem solution.

`#include <bits/stdc++.h>#define ll long long int#define sc1(x) scanf("%d",&x)#define sc2(x,y) scanf("%d%d",&x,&y)#define scll(x) scanf("%lld",&x)#define pint(c) printf("%d",c)#define pll(c) printf("%lld",c)#define ps() printf(" ")#define pn() printf("\n")#define vi vector<int>#define vii vector<pair<int,int> >#define mp make_pair#define pb push_back#define ff(i,n,a) for(i=a;i<n;++i)#define fb(i,n,a) for(i=n,i>=a;--i)const int mxn=1e5+1;const int M=1e9+7;using namespace std;void matmult(long long  a[][2], long long b[][2],long long c[][2]){    int i,j,k;    for(i=0;i<2;i++)    {        for(j=0;j<2;j++)        {            c[i][j]=0;            for(k=0;k<2;k++)            {                c[i][j]+=(a[i][k]*b[k][j])%M;                c[i][j]=c[i][j]%M;            }        }    } }void matpow(long long Z[][2],int n,long long ans[][2]){     long long temp[2][2];    ans[0][0]=1;    ans[1][0]=0;    ans[0][1]=0;    ans[1][1]=1;    int i,j;    while(n>0)    {        if(n&1)        {            matmult(ans,Z,temp);            for(i=0;i<2;i++)                for(j=0;j<2;j++)                    ans[i][j]=temp[i][j];        }        matmult(Z,Z,temp);        for(i=0;i<2;i++)            for(j=0;j<2;j++)                Z[i][j]=temp[i][j];          n=n/2;    }    return;     }long long findFibonacci(long long n){         long long fib;    if(n>2)    {        long long int Z[2][2]={{1,1},{1,0}},result[2][2];        matpow(Z,n-2,result);        fib=result[0][0]*1 + result[0][1]*0;        }    else        fib=n-1;             return fib;}ll getGcd(string s,ll n){    ll b=0;    for(int i=0;i<s.length();++i)        b=(b*10+(s[i]-48))%n;    return __gcd(n,b);}int main(){    ios_base::sync_with_stdio(false);    cin.tie(NULL);    int t;    cin >> t;    assert(1 <= t and t <= 100);    while(t--)    {        string s;        long long n;        cin>>s;        assert(s.size() <= 100000 and s.size() >= 1);        cin>>n;        assert(1 <= n and n <= 1000000000);        ll gc=getGcd(s,n);        cout<<findFibonacci(gc+1)<<"\n";    }    return 0;}`

### Second solution

`#include <bits/stdc++.h>using namespace std;typedef long long ll;const int MAX_N = 1e4 + 14, MOD = 1e9 + 7;struct Mat {    static constexpr int MAX_MAT = 2;    int a[MAX_MAT][MAX_MAT];    explicit Mat(bool emp = false) {        memset(a, 0, sizeof a);        if (emp)            for (int i = 0; i < MAX_MAT; i++)                a[i][i] = 1;    }    const int *operator[](int i) const {        return a[i];    }    int *operator[](int i) {        return a[i];    }    Mat operator+(const Mat &b) {        Mat ret;        for (int i = 0; i < MAX_MAT; i++)            for (int j = 0; j < MAX_MAT; j++)                ret[i][j] = a[i][j] + b[i][j];        return ret;    }    Mat operator*(const Mat &b) {        Mat ret;        for (int k = 0; k < MAX_MAT; k++)            for (int i = 0; i < MAX_MAT; i++)                for (int j = 0; j < MAX_MAT; j++)                    ret[i][j] = (ret[i][j] + (ll) a[i][k] * b[k][j]) % MOD;        return ret;    }    Mat operator^(int b) {        Mat a = *this;        Mat ret(true);        for (; b; b >>= 1, a = a * a)            if (b & 1)                ret = ret * a;        return ret;    }};int main() {    ios::sync_with_stdio(0), cin.tie(0);    Mat base_fib;    base_fib[0][0] = base_fib[0][1] = base_fib[1][0] = 1;    int t;    cin >> t;    while (t--) {        string n;        int m;        cin >> n >> m;        int g = 0;        for (auto c : n)            g = (g * 10ll + c - '0') % m;        g = gcd(g, m);        cout << (base_fib ^ g)[0][1] << '\n';    }}`