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.
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
- Olympics Ranking
- Problem Difficulties
- Chef and Bulb Invention
- Array Filling
- Special Triplets
- Geometry 1
- Charge Scheduling
- Chef and Digits of Large Numbers
- Fat Hut
- Alternating LG Queries