# HackerEarth Fibonacci with GCD problem solution

In this HackerEarth Fibonacci with GCD problem solution, You are given N integers, A1, A2,...AN and Q queries. In each query, you are given two integers L and R(1 <= L <= R <= N). For each query, you have to find the value of:
GCD(F(Al),F(Al+1),F(Al+2)......F(AR))% 10^9 + 7

Can you do it?

## HackerEarth Fibonacci with GCD problem solution.

`#include <bits/stdc++.h>#include<iostream>#include<cstdio>#include<stdlib.h>#include<iomanip>#include<math.h>#include<limits.h>#include<string.h>#include <ctime>#include <deque>#include<algorithm>#include<vector>#include<stack>#include<queue>#include<map>#include<bitset>#include<set>#include <sstream>#include <list>#define mod 1000000007#define MAX 100000000using namespace std;#define scan(a) scanf("%d",&a);#define print(a) printf("%d\n",a);#define mem(a,v) memset(a,v,sizeof(a))#define clr(a) memset(a,0,sizeof(a))#define pb(x) push_back(x)#define sort(a) sort(a.begin(),a.end())#define inf 1e9#define mp(a,b) make_pair(a,b)#define V vector#define S string#define Gu getchar_unlocked#define Pu putchar_unlocked#define Read(n) ch=Gu(); while (ch<'0') ch=Gu(); n=ch-'0'; ch=Gu(); while (!(ch<'0')) {n=10*n+ch-'0'; ch=Gu();}#define Write(n) r=n; chptr=s; *chptr=r%10+'0'; r/=10; for (; r; r/=10) {++chptr; *chptr=r%10+'0'; } Pu(*chptr); for (; chptr!=s; ) Pu(*--chptr);typedef long long LL;typedef long double LD;typedef long L;typedef pair<int,int> pii;const double pi=acos(-1.0);int arr[100010];struct T{    LL gc;}tree[1000050];LL gcd(LL a,LL b){    if(b==0)            return a;    else        return gcd(b,a%b);}void build(int node,int a,int b){    if(a==b)    {        tree[node].gc=arr[a];        return;    }    int mid=(a+b)>>1;    build(2*node,a,mid);    build(2*node+1,mid+1,b);    tree[node].gc = gcd(tree[2*node].gc,tree[2*node+1].gc);    return;}LL query(int node,int i,int j,int a,int b){    if(a<=i && b>=j)    {        return tree[node].gc;    }    if(b<i||a>j)    {        return -1;    }    int mid=(i+j)>>1;    LL t1=query(2*node,i,mid,a,b);    LL t2=query(2*node+1,mid+1,j,a,b);    if(t1==-1 && t2==-1)        return 1;    else if(t1==-1)        return t2;    else if(t2==-1)        return t1;    else        return gcd(t1,t2);}void multiply(LL f[2][2],LL m[2][2]){  LL x =  (f[0][0]*m[0][0] + f[0][1]*m[1][0])%mod;  LL y =  (f[0][0]*m[0][1] + f[0][1]*m[1][1])%mod;  LL z =  (f[1][0]*m[0][0] + f[1][1]*m[1][0])%mod;  LL w =  (f[1][0]*m[0][1] + f[1][1]*m[1][1])%mod;   f[0][0] = x;  f[0][1] = y;  f[1][0] = z;  f[1][1] = w;}void power(LL f[2][2],LL n){    if(n==0||n==1)        return;                   LL m[2][2]={{1,1},{1,0}};    power(f,n/2);    multiply(f,f);    if(n%2!=0)        multiply(f,m);  }LL fib(LL n){    LL f[2][2]={{1,1},{1,0}};    if(n==0)        return 0;    power(f,n-1);    return (f[0][0]%mod);}int main(){    ios_base::sync_with_stdio(false);    int n,q,a,b;    scanf("%d %d",&n,&q);    for(int i=0;i<n;i++)        scanf("%d",&arr[i]);    build(1,0,n-1);    while(q--)    {        scanf("%d %d",&a,&b);        a--;        b--;        int t1=query(1,0,n-1,a,b);        cout<<fib(t1)%mod<<endl;    }       return 0;}`

### Second solution

`#include<bits/stdc++.h>#define MOD 1000000007using namespace std;int arr[100000];int segtree[200000][3]={0};int curmake;int gcd(int a,int b){    if(a==0)        return b;    return gcd(b%a,a);}void makesegment(int nodenow,int l, int r){    if(l==r)    {        segtree[nodenow][0]=arr[l];        segtree[nodenow][1]=-1;        segtree[nodenow][2]=-1;    }    else    {        segtree[nodenow][1]=curmake;        curmake++;        makesegment(curmake-1,l,(l+r)/2);        segtree[nodenow][2]=curmake;        curmake++;        makesegment(curmake-1,(l+r)/2+1,r);        segtree[nodenow][0]=gcd(segtree[segtree[nodenow][1]][0],segtree[segtree[nodenow][2]][0]);    }}int findgcd(int at,int atl,int atr,int l,int r){    int a=-1,b=-1;    if(atl==l  &&  atr==r)        return segtree[at][0];    if((atl+atr)/2>=l)    a=findgcd(segtree[at][1],atl,(atl+atr)/2,l,min(r,(atl+atr)/2));    if((atl+atr)/2+1<=r)    b=findgcd(segtree[at][2],(atl+atr)/2+1,atr,max(l,(atl+atr)/2+1),r);     if(a==-1)        return b;    if(b==-1)        return a;            return gcd(a,b);}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]);                c[i][j]=c[i][j]%MOD;            }        }    }}long long matpow(long long a[][2],int n){    long long fib;    long long ans[2][2]={{1,0},{0,1}},temp[2][2];    int i,j;    while(n>0)    {        if(n&1)        {            matmult(ans,a,temp);            for(i=0;i<2;i++)            {                for(j=0;j<2;j++)                {                    ans[i][j]=temp[i][j];                }            }        }        matmult(a,a,temp);        for(i=0;i<2;i++)        {                for(j=0;j<2;j++)                {                        a[i][j]=temp[i][j];                }        }        n=n/2;    }    fib=(ans[0][0]*2+ans[0][1]);//modify here too    fib=fib%MOD;    return fib;}int main(){        ios::sync_with_stdio(false);    int n,q;    cin>>n>>q;    assert(1<=n && n<=100000 && 1<=q && q<=100000);    int i;    for(i=0;i<n;i++)    {        cin>>arr[i];            assert(1<=arr[i] && arr[i]<=1000000000);    }    curmake=1;      makesegment(0,0,n-1);    while(q--)    {        long long int a[2][2]={{1,1},{1,0}};        int l,r;        cin>>l>>r;        assert(1<=l && l<=n && 1<=r && r<=n && l<=r);        l--;        r--;        int g=findgcd(0,0,n-1,l,r);        long long fib;        g--;         if(g>2)            fib=matpow(a,g-2);        else if(g>0)            fib=g;        else             fib=1;        cout<<fib<<endl;    }    return 0;}`