Problem 2: Fibonacci GCD

Points:

Small Case: 8 Answer: 144

Large Case: 16 Answer: 210345902

A Fibonacci sequence is generated by adding the previous two terms. By starting with 1 and 1, the first 10 terms will be:

1,1, 2, 3, 5, 8, 13, 21, 34, 55, ...

The recursive sequence is given by :

F(n)=F(n-1)+F(n-2)

The GCD of 2 numbers is the largest number which divides those two numbers completely ( i.e leaves no remainder).

The problem is to find the GCD(F(n),F(m)) mod 1000000007 ?

Small Case: n = 156 , m = 192

Large Case: n = 1234567890 , m = 9876543210

Solution:

The relation used to solve this problem is:
gcd(F(m),F(n)) = F(gcd(m,n))

We can find gcd(m,n) by euclidian algorithm , and then we have to find the value of F(gcd(m,n))%1000000007 .
For solving this we use the matrix representation of (x+2)th fibonacci number, which is :

which can be done in O(log(n)) time complexity.

Reference: Arthur T. Benjamin and Jennifer J. Quinn, Revisiting Fibonacci and Related Sequences, 2004

Code:

#include<iostream>
#include<cstdlib>
#include<cstdio>
#include<vector>
#include<map>
#define ll long long int
#define MOD 1000000007ll
using namespace std;
ll n;
ll multiply(ll ans[][11],ll c[][11],ll n)
{
    ll ans1[11][11]={0};
    for(ll i=0;i<n;i++)
        for(ll j=0;j<n;j++)
        {
            ll x=0;
            for(ll k=0;k<n;k++)
            {
                x=(x+(ans[i][k]*c[k][j])%MOD)%MOD;
            }
            ans1[i][j]=x;
        }
    for(ll i=0;i<n;i++)
        for(ll j=0;j<n;j++)
            ans[i][j]=ans1[i][j];
    return 0;
}
ll power(ll y,ll n,ll c[][11],ll ans[][11])
{
    for(ll i=0;i<n;i++)
        for(ll j=0;j<n;j++)
            if(i==j)
                ans[i][j]=1;
            else
                ans[i][j]=0;
    while(y)
    {
        if(y&1)
        {
            multiply(ans,c,n);
        }
        multiply(c,c,n);
        y>>=1;
    }
    return 0;
}
ll gcd(ll a,ll b)
{
    if(b==0)
        return a;
    return gcd(b,a%b);
}
int main()
{
    ll j,i,x1,y1,n,x,b[11][11]={0},c[11][11]={0},ans[11][11]={0};
        n=2;
        for(i=n-1;i>=0;i--)
        {
            c[i][0]=1;
        }
        for(i=0;i<n;i++)
        {
            b[0][i]=1;
        }
        for(i=1;i<n;i++)
            for(j=0;j<n;j++)
                if((i-j)==1)
                    b[i][j]=1;
                else
                    b[i][j]=0;
        scanf("%lld %lld",&x1,&y1);
        x=gcd(x1,y1);
        if(x<=n)
        {
            printf("%lld\n",c[n-x][0]);
        }
        else
        {
            power(x-n,n,b,ans);
            ll res=0;
            for(i=0;i<n;i++)
                res=(res+(ans[0][i]*c[i][0])%MOD)%MOD;
            printf("%lld\n",res);
        }
    return 0;
}