# August Long Challenge Alternating LG Queries Solution

Page Contents

## Alternating LG Queries Solution

You are given an array AA consisting of NN integers. You have to answer QQ queries of the following two types:

• 11 LL RR (R>L)(R>L) which asks you to find gcd(AL,lcm(AL+1,gcd(AL+2,…,((R−L)mod2==1?gcd(AL,lcm(AL+1,gcd(AL+2,…,((R−L)mod2==1? gcd(AR−1,AR):lcm(AR−1,AR))…)))gcd(AR−1,AR):lcm(AR−1,AR))…))).
• 22 LL RR (R>L)(R>L) which asks you to find the same as above but lcmlcm swapped with gcdgcd and vice-versa.

Here lcm(a,b)lcm(a,b) and gcd(a,b)gcd(a,b) denotes the least common multiple and greatest common divisor of two integers aa and bb respectively.

Example: Consider the array AA = [2,4,8,16,32,64][2,4,8,16,32,64].

• Suppose a query is of the form 11 11 66, so it asks you to find: gcd(2,lcm(4,gcd(8,lcm(16,gcd(32,64)))))gcd(2,lcm(4,gcd(8,lcm(16,gcd(32,64))))).
• Suppose a query is of the form 22 11 55, so it asks you to find: lcm(2,gcd(4,lcm(8,gcd(16,32))))lcm(2,gcd(4,lcm(8,gcd(16,32)))).

Note: Since input-output is large, prefer using fast input-output methods.

Also See: August Long Challenge 2021 Solutions

### Input Format

• The first line of the input contains a single integer TT denoting the number of test cases. The description of TT test cases follows.
• Each testcase contains Q+2Q+2 lines of input.
• The first line of each test case contains two space-separated integers, NN and QQ.
• The second line of each test case contains NN space-separated integers A1,A2,…,ANA1,A2,…,AN.
• QQ lines follow. For each valid ii, the ithith of these lines contains three space-separated integers Typei,Li,RiTypei,Li,Ri, the type and parameters of the ithith query.

### Output Format

For each query, output in a single line answer to the problem.

### Constraints

• 1≤T≤31≤T≤3
• 2≤N≤2⋅1052≤N≤2⋅105
• 1≤Q≤2⋅1051≤Q≤2⋅105
• 1≤Ai≤1091≤Ai≤109
• 1≤Typei≤21≤Typei≤2
• 1≤Li<Ri≤N1≤Li<Ri≤N
• The sum of NN over all test cases does not exceed 2⋅1052⋅105.
• The sum of QQ over all test cases does not exceed 2⋅1052⋅105.

• 2≤N≤6302≤N≤630
• The sum of NN over all test cases does not exceed 630630.
• Time limit: 11 sec

• Original constraints
• Time limit: 1.51.5 sec

### Sample Input 1

``````1
6 3
2 4 8 16 32 64
1 1 6
2 1 5
1 5 6
``````

### Sample Output 1

``````2
4
32
``````

### Explanation

Test case 11: The answer for the first query is =gcd(2,lcm(4,gcd(8,lcm(16,gcd(32,64)))))=gcd(2,lcm(4,gcd(8,lcm(16,gcd(32,64))))) == gcd(2,lcm(4,gcd(8,lcm(16,32))))gcd(2,lcm(4,gcd(8,lcm(16,32)))) = gcd(2,lcm(4,gcd(8,32)))gcd(2,lcm(4,gcd(8,32))) = gcd(2,lcm(4,8))gcd(2,lcm(4,8)) = gcd(2,8)gcd(2,8) = 22.

The answer for the second query is =lcm(2,gcd(4,lcm(8,gcd(16,32))))=lcm(2,gcd(4,lcm(8,gcd(16,32)))) = lcm(2,gcd(4,lcm(8,16)))lcm(2,gcd(4,lcm(8,16))) = lcm(2,gcd(4,16))lcm(2,gcd(4,16)) = lcm(2,4)lcm(2,4) = 44.

## Solution:

Program C++:

```#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define vi vector <int>
#define vll vector < ll >
#define pb push_back
#define endl '\n'
#define max3(a,b,c) max(max(a,b),c)
#define min3(a,b,c) min(min(a,b),c)
#define answer(ans) cout << ans << '\n' ;
#define ansyes cout << "YES\n" ;
#define ansno cout << "NO\n" ;
#define pll pair<ll,ll>
#define ff first.first
#define fs first.second

#define int ll

ll gcd(ll a ,ll b)
{
if(b==0) return a;
else return gcd(b,a%b);
}

ll lcm(ll a,ll b)
{
return ((a*b)/gcd(a,b));
}

void find_prime(vll &v,int n,vll &reach,vector <bool> &flag)
{
ll pre=gcd(v[0],v[1]),suff;
for (ll i=0;i<n-2;i++)
{
suff=gcd(v[i+1],v[i+2]);
if (pre==1 && suff==1 && gcd(v[i],v[i+2])==1)
{
flag[i]=true;
}
pre=suff;
}
int last=n;
for (ll i=n-1;i>=0;i--)
{
if(flag[i]) last=i;

reach[i]=last;
}
}

void doGcd(vll &v,vll &reach,int n,vll &getgcd,vector <bool> &flag)
{
ll i,ans=1,k=0;
getgcd[n-1]=v[n-1];
for (i=n-2;i>=0;i--)
{
if(k%2)
{
ans = getgcd[i] = gcd(v[i],ans);
}
else
{
ans = getgcd[i] = lcm(v[i],ans);
}
k++;
if(flag[i])
{
k=0;
ans=1;
}
}

}

void workgcd(vector < pair< pll,ll > > &vg , vll &v , int n,vll &sol,int h,vll &reach,vll &getgcd)
{
int k=0,len=vg.size(),i,j,ans=1,l,s;

while(k<len)
{
l=k+1;
while(l<len && vg[l].ff==vg[l-1].ff) l++;
l--;
ans=v[vg[k].ff];
s=k;
while(vg[k].fs==vg[k].ff)
{
sol[vg[k].second]=ans;
k++;
}
if(k==len) break;
if(vg[k].ff==vg[s].ff)
{

for (i=vg[k].ff-1,j=h;i>=vg[l].fs;i--,j++)
{

if(j%2)
{
ans = lcm(ans,v[i]);
}
else
{
ans = gcd(ans,v[i]);
}
// if(reach[vg[k].fs]!=reach[vg[k].ff]) i=vg[k].fs,ans=v[i] ;
if(i==vg[k].fs)
{
sol[vg[k].second]=ans;
k++;
}
}
}
}
return ;
}

ll f1(ll a, ll b, vll &v)
{
ll ans=v[b],j=1;
for (ll i=b;i>=a;i--)
{
if(j%2)
{
ans=gcd(ans,v[i]);
}
else
{
ans=lcm(ans,v[i]);
}
j++;
}
return ans;
}

void solve()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);

int n,q,i,j;
cin >> n >> q;
vector <ll> v(n),sol(q),reach(n,n);
vector < pair< pll,ll > > vg,vl;

for (i=0;i<n;i++)
{
cin >> v[i];
}
vector <bool> flag(n,false);
find_prime(v,n,reach,flag);
vector <ll> getgcd(n);
doGcd(v,reach,n,getgcd,flag);

ll t,a,b;
for (i=0;i<q;i++)
{
cin >> t >> a >> b ;
if (t==1)
{
if((b-a )%2)
{
if(flag[a-1]) sol[i]=1;
else if(reach[b-1]!=reach[a-1])
{
ll k=reach[a-1];
if((k-a+1)%2==0) sol[i]=getgcd[a-1];
else vg.push_back({{b-1,a-1},i});
}
else vg.push_back({{b-1,a-1},i});
}
else
{
if(flag[a-1]) sol[i]=1;
else if(reach[b-1]!=reach[a-1])
{
ll k=reach[a-1];
if((k-a+1)%2==0) sol[i]=getgcd[a-1];
else vl.push_back({{b-1,a-1},i});
}
else
vl.pb({{b-1,a-1},i});
}
}
else{
if((b-a)%2==0)
{
if(flag[a]) sol[i]=lcm(v[a],v[a-1]);
else if(reach[b-1]!=reach[a-1])
{
ll k=reach[a-1];
if((k-a+1)%2) sol[i]=getgcd[a-1];
else vg.push_back({{b-1,a-1},i});
}
else vg.push_back({{b-1,a-1},i});
}

else
{
if(flag[a]) sol[i]=lcm(v[a],v[a-1]);
else if(reach[b-1]!=reach[a-1])
{
ll k=reach[a-1];
if((k-a+1)%2) sol[i]=getgcd[a-1];
else vl.push_back({{b-1,a-1},i});
}
else vl.pb({{b-1,a-1},i});
}
}
}
sort(vg.rbegin(),vg.rend());
sort(vl.rbegin(),vl.rend());

workgcd(vg,v,n,sol,0,reach,getgcd);
workgcd(vl,v,n,sol,1,reach,getgcd);

for (i=0;i<q;i++)
{
cout << sol[i] << "\n";
}

return ;
}

int32_t main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);

int t=1;
cin >> t;
while(t--)
{
solve();
}

return 0;
}
```