code. compile. run. debug. share.
Source Code
Language
#include <iostream>
#define ll long long
using namespace std;
#define bigNum 1000000007
typedef struct matrix2x2{ // for tranformation matrix
ll a11,a12,a21,a22;
}matrix2x2;
typedef struct matrix2x1{
ll a11,a21;
}matrix2x1;
matrix2x2 multiply2x2(ll n,matrix2x2 trnf){ // calculating nth power of tranformation matrix
if(n==1) return trnf;
matrix2x2 temp = multiply2x2(n/2,trnf);
matrix2x2 t2;
t2.a11 = (temp.a11*temp.a11 + temp.a12*temp.a21)%bigNum;
t2.a12 = (temp.a11*temp.a12 + temp.a12*temp.a22)%bigNum;
t2.a21 = (temp.a21*temp.a11 + temp.a22*temp.a21)%bigNum;
t2.a22 = (temp.a21*temp.a12 + temp.a22*temp.a22)%bigNum;
if(n%2 == 0) return t2;
else {
matrix2x2 tTemp = t2;
tTemp.a11 = t2.a21;
tTemp.a12 = t2.a22;
tTemp.a21 = (t2.a11 + t2.a21)%bigNum;
tTemp.a22 = (t2.a21 + t2.a22)%bigNum;
return tTemp;
}
}
ll gcd(ll a,ll b)
{
if (b == 0)
return a;
return gcd(b, a % b);
}
ll fib(ll n){
if(n==1) return 1;
if(n==2) return 1;
n-=1;
matrix2x2 trnf;
trnf.a11 = 0;
trnf.a12 = 1;
trnf.a21 = 1;
trnf.a22 = 1;
matrix2x2 answer = multiply2x2(n-1,trnf);
return (answer.a21+answer.a22)%bigNum;
}
ll build(ll *tree,ll* arr,ll s,ll e,ll index){
if(s==e){
tree[index] = fib(arr[s]);
return tree[index];
}
ll mid = (s+e)/2;
ll x = build(tree,arr,s,mid,2*index);
ll y= build(tree,arr,mid+1,e,2*index+1);
tree[index] = gcd(x,y);
return tree[index];
}
ll query(ll* tree,ll s,ll e,ll qS,ll qE,ll index){
// disjoint overlap
if(s>qE || e<qS) return -1;
if(qS<=s && qE>=e){
return tree[index];
}
ll mid = (s+e)/2;
ll x= query(tree,s,mid,qS,qE,2*index);
ll y= query(tree,mid+1,e,qS,qE,2*index+1);
if(x==-1) return y;
if(y== -1) return x;
return gcd(x,y);
}
int main() {
//for(ll i = 1;i<50;i++) cout << fib(i);
ll n ,q;
cin >> n >>q;
ll *arr = new ll [n];
for(ll i = 0;i<n;i++) cin >> arr[i];
ll *tree = new ll[4*n+1];
build(tree,arr,0,n-1,1);
for(ll i = 0;i<q;i++){
ll l,r;
cin >> l >> r;
cout << query(tree,0,n-1,l-1,r-1,1) << endl;
}
}
Compiling Program...
Standard Input:
Interactive Console
Text
Program is not being debugged. Click "Debug" button to start program in debug mode.
| # | Function | File:Line |
|---|
| Variable | Value |
|---|
| Register | Value |
|---|
| Expression | Value |
|---|
| # | Description |
|---|