August Long Challenge Alternating LG Queries Solution

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.

Subtasks

Subtask #1 (10 points):

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

Subtask #2 (90 points):

  • 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;
}

Codechef Long Challenges

August Long Challenge 2021 Solutions

July Long Challenge 2021 Solutions

Leave a Comment