PROBLEM LINK:
Contest Division 1
Contest Division 2
Contest Division 3
Practice
Setter: Daanish Mahajan
Tester: Miten Shah
Editorialist: Taranpreet Singh
DIFFICULTY
Medium
PREREQUISITES
Segment Tree, Number Theory
PROBLEM
Given an array A with N integers, you have to answer Q queries, where each query may be one of the following form
- 1 L R (R > L) which asks you to find \gcd(A_L, lcm(A_{L + 1}, \gcd(A_{L + 2}, ... , ((R - L) \bmod 2 == 1 ? \gcd(A_{R - 1}, A_{R}) : lcm(A_{R - 1}, A_{R}))\ldots))).
- 2 L R (R > L) which asks you to find the same as above but lcm swapped with \gcd and vice-versa.
EXPLANATION
Different Problem
Let’s forget the original problem for this section and try to solve following one.
A function f is defined as \displaystyle f_{x, y}(z) = min(x, max(y, z)) for some given x and y. For example, f_{10,3}(z) is a function representing min(10, max(3, z))
You are given four integers x_1, y_1, x_2, y_2 and you need to find any two integers x_3 and y_3 such that f_{x_1, y_1}(f_{x_2, y_2}(z)) = f_{x_3, y_3}(z) holds for all possible values of z
Give this problem a thought, as solving this problem is crucial to solving the original problem.
We have min(x_1, max(y_1, min(x_2, max(y_2, z)))) = min(x_3, max(y_3, z)).
The issue here is that we need to somehow swap the inner min and max. The distributive property comes useful here. We can write max(a, min(b, c)) = min(max(a, b), max(a, c)). Applying distributive property on max(y_1, min(x_2, max(y_2, z))), we get
min(x_1, min(max(y_1, x_2), max(y_1, max(y_2, z)))) = min(x_3, max(y_3, z)). Now we can apply associative property to rearrange the expression into
min(x_1, max(y_1, x_2), max(y_1, y_2, z)) = min(x_3, max(y_3, z))
min(min(x_1, max(y_1, x_2)), max(max(y_1, y_2), z)) = min(x_3, max(y_3, z))
Now, we actually compare terms on both sides, which would imply
x_3 = min(x_1, max(y_1, x_2))
y_3 = max(y_1, y_2). Or we can write y_3 = min(x_1, max(y_1, y_2)) as we know that later we have to take min with x_1.
Using functional representation, we can see that the values x_3 = f_{x_1, y_1}(x_2) and y_3 = f_{x_1, y_1}(y_2) are the solution to this problem.
Similarly, if we have g_{x, y}(z) = max(y, min(x, z)), then we could have solved the problem same way, obtaining x_3 = g_{x_1, y_1}(x_2) and y_3 = g_{x_1, y_1}(y_2)
Problem similar to original problem
Replace gcd by min and lcm by max in original problem statement. We have to answer queries of that type now.
Since we have to answer range queries, the possible data structures here are segment tree, sparse table or any other similar structure. One common thing in above structures is how they compute some quantity for whole range quickly, and we divide the query range into O(log(R-L)) ranges, and try to merge the results of those ranges.
So here, assuming we choose segment tree, Consider a node representing interval [L, R]. We shall store two constants X and Y such that function f_{X,Y} represents the answer to query for this range. Specifically, min(A_L, max(A_{L+1}, min(A_{L+2}, ... ((R - L) \bmod 2 == 0 ? \min(A_{R}, z) : max(A_{R}, z))\ldots))) = f_{X, Y}(z).
It is basically computing the net effect of applying merging operation with all elements in range quickly.
Let’s say we have two nodes representing ranges [L, M] and [M+1, R] represented by functions f_{x_1, y_1} and f_{x_2, y_2}, we need to find values X and Y such that f_{x_1, y_1}(f_{x_2, y_2}(z)) = f_{X, Y}(z) holds. It is precisely same to the problem we discussed above.
Hence, if we can choose appropriate values for leaf nodes, we now know how to merge results of two nodes, thus computing the whole tree before queries and answering queries in O(log(N)) time.
We shall store two function parameters at each node. Specifically, we shall store X_1 and Y_1 such that f_{X_1, Y_1} answers our query of type 1. Similarly, we shall store integers X_2 and Y_2 such that g_{X_2, Y_2} answers our query of type 2
Choosing X_1, Y_1, X_2 and Y_2 for leaf nodes
Let’s say we have a leaf node representing range [p, p]. We need to choose X_1 and Y_1 such that min(A_p, z) = f_{X_1, Y_1}(z). We can choose X_1 = A_p and Y_1 = -\infin
We need to choose X_2 and Y_2 such that max(A_p, z) = g_{X_2, Y_2}(z) holds for all z. We can choose X_2 = \infin and Y_2 = A_p.
Edge case
When merging two child nodes, we need to check if the left child represent an even number of sub-operations or odd number of operations, as the next sub-operation (min or max) to be applied depends upon the parity of length of range covered by left child.
Specifically, if range length of left child is even, we need to find X_1, Y_1 such that f_{X_1, Y_1}(z) = f_{x_1, y_1}(f_{x_2, y_2}(z)). But if the range length of left child is odd, we have f_{X_1, Y_1}(z) = f_{x_1, y_1}(g_{x_2, y_2}(z)).
Composition f_{x_1, y_1}(g_{x_2, y_2}(z)) is easy to calculate, as the inner two max operations can be merged after expanding. Similarly, g_{x_1, y_1}(f_{x_2, y_2}(z)) is evaluated by merging inner min operations.
Relation to original problem
Have a careful read of section Fundamental theorem of Arithmetic especially how they write
- gcd operation as minimum of values of exponents in prime factorization of two numbers
- lcm operation has maximum of values of exponents in prime factorization of two numbers
The exponent of prime p_1 is independent of exponent of a different prime p_2.
So, it is possible to solve the original problem by
- Considering all primes one by one
- For prime p, define B_i = max(j : p^j | A_i), i.e. maximum power of p which divides A_i.
- Compute the answer for all primes for each query range using above problem.
- Answers computed for each prime are the exponents of those primes in answer of original query.
Let’s assume array A = [12,6,4,8,9,2,3]. When solving for p = 2, we have B = [2,1,2,3,0,1,0] and for p = 3, we have B = [1,1,0,0,2,0,1].Let’s say we compute answer A_2 for p = 2 and A_3 for p = 3.
Then the answer to our original problem query would be 2^{A_{2}} * 3^{A_3}
But doing this for every prime for every query leads to time complexity O(Q*max(A_i)*log(N)) which is too slow.
Magic of multiplicative functions
Have a look at this explanation of Multiplicative functions.
We can replace the min function by gcd and max function by lcm in our previous solution, and compute the answer for all primes simultaneously.
This works because in each prime, gcd and lcm acts on exponents of different primes independently.
Hence, we adapt our segment tree solution by replacing min with gcd and max with lcm to solve the problem.
Implementation caveats
- Earlier we choose initial values for leaf nodes assuming min and max operation. Now f_{X_1, Y_1}(z) = gcd(X_1, lcm(Y_1, z)). We need to choose values X_1, Y_1 such that f_{X_1, Y_1}(z) = gcd(A_i, z) for i-th leaf. We can choose X_1 = A_i and Y_1 = 1.
- Similarly, we choose X_2 = 0 and Y_2 = A_i such that g_{X_2, Y_2}(z) = lcm(Y_2, gcd(X_2, z)) = lcm(A_i, z)
- 0 here satisfies the properties of \infin and 1 works for -\infin, as gcd(1, x) = 1, lcm(1, x) = x and gcd(x, 0) = x and lcm(x, 0) = 0 (Technically it is not defined, but assuming this is consistent with our problem.
- It is possible that when we distributed lcm operation, we may end up computing lcm of three integers of values close to 10^9, which can result in lcm being close to 10^27 overflowing even long data type. Easy work around is to apply gcd with every term where it can be applied. This issue happens when computing f_{x_1, y_1}(g_{x_2, y_2}(z))
TIME COMPLEXITY
The time complexity is O((N+Q)*log(N)*log(A_i)) per test case theoretically, but works faster in practice as log(A_i) to compute gcd and lcm is the worst case scenario.
SOLUTIONS
Setter's Solution
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define pb push_back
#define rb pop_back
#define ti tuple<int, int, int>
#define pii pair<int, int>
#define pli pair<ll, int>
#define pll pair<ll, ll>
#define mp make_pair
#define mt make_tuple
using namespace std;
const int maxn = 2e5 + 10, maxq = 2e5, maxtn = 2e5, maxtq = 2e5, maxv = 1e9, minv = 1, maxt = 3;
const string newln = "\n", space = " ";
pll seg[2][2 * maxn];
pll lazy[2][2 * maxn];
ll a[maxn];
ll store[maxq];
vector<int> v[maxn];
pii desp[maxq];
pll base = {1, 0};
void convolve(pll& p, pll p2, pll p1){
p.second = __gcd(p2.second, p1.second);
ll gd = __gcd(p2.second, p1.first);
p.first = p2.first * (gd / __gcd(p2.first, gd));
}
void lazyupd(int& id, int n, int s, int e){
if(lazy[id][n] == base)return;
convolve(seg[id][n], seg[id][n], lazy[id][n]);
if(s != e){
convolve(lazy[id][2 * n + 1], lazy[id][2 * n + 1], lazy[id][n]);
convolve(lazy[id][2 * n + 2], lazy[id][2 * n + 2], lazy[id][n]);
}
lazy[id][n].first = 1; lazy[id][n].second = 0;
}
void upd(int& id, int n, int s, int e, int& ul, int& ur, pll& p){
lazyupd(id, n, s, e);
if(ul > e || ur < s || ul > ur)return;
if(s >= ul && e <= ur){
convolve(lazy[id][n], lazy[id][n], p);
lazyupd(id, n, s, e);
return;
}
int m = (s + e) >> 1;
upd(id, 2 * n + 1, s, m, ul, ur, p); upd(id, 2 * n + 2, m + 1, e, ul, ur, p);
convolve(seg[id][n], seg[id][2 * n + 1], seg[id][2 * n + 2]);
}
pll query(int& id, int n, int s, int e, int& ql, int& qr){
if(ql > e || qr < s || ql > qr)return base;
lazyupd(id, n, s, e);
if(s >= ql && e <= qr){
return seg[id][n];
}
int m = (s + e) >> 1;
pll p2 = query(id, 2 * n + 1, s, m, ql, qr), p1 = query(id, 2 * n + 2, m + 1, e, ql, qr);
pll rs; convolve(rs, p2, p1);
return rs;
}
int main()
{
ios_base :: sync_with_stdio(0); cin.tie(0); cout.tie(0);
int t, n, q, ty, l, r;
cin >> t;
while(t--){
cin >> n >> q;
for(int i = 0; i < 2 * n + 10; i++){
for(int j = 0; j < 2; j++){
seg[j][i].first = lazy[j][i].first = 1;
seg[j][i].second = lazy[j][i].second = 0;
}
}
for(int i = 0; i < n; i++){
v[i].clear();
cin >> a[i];
}
for(int i = 0; i < q; i++){
cin >> ty >> l >> r;
ty--; l--; r--;
v[r].pb(i);
desp[i] = {ty, l};
}
for(int i = 1; i < n; i++){
for(int id : v[i]){
int tys = desp[id].first, l = desp[id].second; // 0 - gcd
int tye = (i - l) % 2 ? tys : 1 - tys;
ll ans = a[i];
if(i - l + 1 <= 10){
// bruteforce
int op = tye;
for(int j = i - 1; j >= l; j--){
ll gd = __gcd(a[j], ans);
if(op == 0)ans = gd;
else ans = ans * (a[j] / gd);
op = 1 - op;
}
}else{
// segtree query
int ql = l, qr = i - 1;
if(tye == 1)qr--;
if(tys == 0)ql++;
assert((qr - ql) & 1);
int sid = ql & 1;
ql /= 2; qr = (qr - 1) / 2;
pll rs = query(sid, 0, 0, n / 2, ql, qr);
if(tye == 1)ans = ans * (a[i - 1] / __gcd(ans, a[i - 1]));
assert(ans > 0);
ans = __gcd(ans, rs.second);
ans = ans * (rs.first / __gcd(ans, rs.first));
assert(ans > 0);
if(tys == 0)ans = __gcd(a[l], ans);
}
store[id] = ans;
}
// segtree upd
int sid = (i - 1) & 1, up = (i - 1) / 2;
pll uv = {a[i - 1], a[i]};
upd(sid, 0, 0, n / 2, up, up, uv); // gcd with a[i] followed by lcm with a[i - 1]
}
for(int i = 0; i < q; i++){
cout << store[i] << endl;
}
}
}
Tester's Solution
// created by mtnshh
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define pb push_back
#define rb pop_back
#define ti tuple<int, int, int>
#define pii pair<int, int>
#define pli pair<ll, int>
#define pll pair<ll, ll>
#define mp make_pair
#define mt make_tuple
#define rep(i,a,b) for(ll i=a;i<b;i++)
#define repb(i,a,b) for(ll i=a;i>=b;i--)
#define err() cout<<"--------------------------"<<endl;
#define errA(A) for(auto i:A) cout<<i<<" ";cout<<endl;
#define err1(a) cout<<#a<<" "<<a<<endl
#define err2(a,b) cout<<#a<<" "<<a<<" "<<#b<<" "<<b<<endl
#define err3(a,b,c) cout<<#a<<" "<<a<<" "<<#b<<" "<<b<<" "<<#c<<" "<<c<<endl
#define err4(a,b,c,d) cout<<#a<<" "<<a<<" "<<#b<<" "<<b<<" "<<#c<<" "<<c<<" "<<#d<<" "<<d<<endl
#define all(A) A.begin(),A.end()
#define allr(A) A.rbegin(),A.rend()
#define ft first
#define sd second
#define V vector<ll>
#define S set<ll>
#define VV vector<V>
#define Vpll vector<pll>
#define endl "\n"
long long readInt(long long l,long long r,char endd){
long long x=0;
int cnt=0;
int fi=-1;
bool is_neg=false;
while(true){
char g=getchar();
// char g = getc(fp);
if(g=='-'){
assert(fi==-1);
is_neg=true;
continue;
}
if('0'<=g && g<='9'){
x*=10;
x+=g-'0';
if(cnt==0){
fi=g-'0';
}
cnt++;
assert(fi!=0 || cnt==1);
assert(fi!=0 || is_neg==false);
assert(!(cnt>19 || ( cnt==19 && fi>1) ));
} else if(g==endd){
if(is_neg){
x= -x;
}
// cerr << x << " " << l << " " << r << endl;
assert(l<=x && x<=r);
return x;
} else {
assert(false);
}
}
}
string readString(int l,int r,char endd){
string ret="";
int cnt=0;
while(true){
char g=getchar();
// char g=getc(fp);
assert(g != -1);
if(g==endd){
break;
}
cnt++;
ret+=g;
}
assert(l<=cnt && cnt<=r);
return ret;
}
long long readIntSp(long long l,long long r){
return readInt(l,r,' ');
}
long long readIntLn(long long l,long long r){
return readInt(l,r,'\n');
}
string readStringLn(int l,int r){
return readString(l,r,'\n');
}
string readStringSp(int l,int r){
return readString(l,r,' ');
}
const int maxt = 3, maxn = 2e5;
const int maxA = 1e9;
const int maxq = 2e5;
const ll N = 200005;
ll __lcm(ll a, ll b){
return (a * (b / __gcd(a, b)));
}
// Segment Tree
struct segTree{
pll t[2][4*N];
pll def = {-1,-1};
void init(){
rep(i,0,4*N) t[0][i]=def, t[1][i]=def;
}
pll combine(pll p2, pll p1){
if(p1.ft == -1)
return p2;
if(p2.ft == -1)
return p1;
pll p;
p.sd = __gcd(p2.sd, p1.sd);
p.ft = __lcm(p2.ft, __gcd(p2.sd, p1.ft));
return p;
}
pll query(ll id, ll v, ll tl, ll tr, ll l, ll r) {
if (l > r)
return def;
if (l == tl && r == tr) {
return t[id][v];
}
ll tm = (tl + tr) / 2;
return combine(query(id, v*2, tl, tm, l, min(r, tm)), query(id, v*2+1, tm+1, tr, max(l, tm+1), r));
}
void update(ll id, ll v, ll tl, ll tr, ll pos, pll new_val) {
if (tl == tr) {
t[id][v] = new_val;
} else {
ll tm = (tl + tr) / 2;
if (pos <= tm)
update(id, v*2, tl, tm, pos, new_val);
else
update(id, v*2+1, tm+1, tr, pos, new_val);
t[id][v] = combine(t[id][v*2],t[id][v*2+1]);
}
}
};
ll A[N];
segTree seg;
void solve(ll n, ll q){
rep(i,1,n+1){
A[i] = (i == n ? readIntLn(1, maxA) : readIntSp(1,maxA));
}
seg.init();
ll seg_n = (n+1)/2;
rep(i,1,n+1){
if(i&1) seg.update(0,1,1,seg_n,(i+1)/2,{A[i],A[i+1]});
else seg.update(1,1,1,seg_n,(i+1)/2,{A[i],A[i+1]});
}
while(q--){
ll t = readIntSp(1, 2), l = readIntSp(1, n), r = readIntLn(1, n);
assert(r > l);
t--;
ll t_r = (r - l) % 2 ? t : 1 - t;
ll t_l = 0;
if(t == 0) t_l = 1;
if((r - l) < 3){
// do something
ll p = A[r];
ll op = t_r;
repb(i,r-1,l){
if(op) p = __lcm(p, A[i]);
else p = __gcd(p, A[i]);
op ^= 1;
}
cout << p << endl;
continue;
}
ll ans = A[r];
r--;
if(t_l) l++;
if(t_r) r--;
ll id = (l + 1) % 2;
pll p = seg.query(id, 1, 1, seg_n, (l+1)/2, r/2);
if(t_r){
r++;
ans = __lcm(ans, A[r]);
}
ans = __lcm(p.ft, __gcd(p.sd, ans));
if(t_l){
l--;
ans = __gcd(ans, A[l]);
}
cout << ans << endl;
}
}
int main(){
ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
ll t = readIntLn(1, 3);
ll tot_n = 0, tot_q = 0;
while(t--){
ll n = readIntSp(1, maxn), q = readIntLn(1, maxq);
tot_n += n;
tot_q += q;
solve(n, q);
}
assert(tot_n <= maxn);
assert(tot_q <= maxq);
}
Editorialist's Solution
import java.util.*;
import java.io.*;
class ALTLG{
//SOLUTION BEGIN
// long IINF = (long)1e18;
void pre() throws Exception{}
void solve(int TC) throws Exception{
int N = ni(), Q = ni();
long[] A = new long[N];
for(int i = 0; i< N; i++)A[i] = nl();
Node root = build(A, 0, N-1);
for(int q = 0; q< Q; q++){
int ty = ni(), L = ni()-1, R = ni()-1;
Node ans = query(root, L, R, 0, N-1);
if(ty == 1)pn(ans.q1(A[R]));
else pn(ans.q2(A[R]));
}
}
long q1(long[] A, int l, int r) throws Exception{
if(l == r)return A[l];
return gcd(A[l], q2(A, l+1, r));
}
long q2(long[] A, int l, int r) throws Exception{
if(l == r)return A[l];
return lcm(A[l], q1(A, l+1, r));
}
void dbg(Object... o){System.out.println(Arrays.deepToString(o));}
Node build(long[] A, int l, int r) throws Exception{
if(l == r)return new Node(l, A[l]);
int mid = (l+r)/2;
return new Node(build(A, l, mid), build(A, mid+1, r));
}
Node query(Node node, int l, int r, int ll, int rr) throws Exception{
if(l == ll & r == rr)return node;
int mid = (ll+rr)/2;
if(r <= mid)return query(node.left, l, r, ll, mid);
if(l > mid)return query(node.right, l, r, mid+1, rr);
return new Node(query(node.left, l, mid, ll, mid), query(node.right, mid+1, r, mid+1, rr));
}
class Node{
int le, ri;
long lo1, hi1;
long lo2, hi2;
Node left, right;
public Node(int i, long x){
le = ri = i;
lo1 = 1;hi1 = x;
lo2 = x;hi2 = 0;
left = null;
right = null;
}
public Node(Node l, Node r) throws Exception{
this.left = l;
this.right = r;
this.le = l.le;
this.ri = r.ri;
if((l.ri-l.le+1)%2 == 0){
this.lo1 = l.q1(r.lo1);
this.hi1 = l.q1(r.hi1);
this.lo2 = l.q2(r.lo2);
this.hi2 = l.q2(r.hi2);
}else{
this.lo1 = l.q1(r.lo2);
this.hi1 = l.q1(r.hi2);
this.lo2 = l.q2(r.lo1);
this.hi2 = l.q2(r.hi1);
}
}
long q1(long x) throws Exception{
return gcd(hi1, lcm(lo1, gcd(hi1, x)));//Inner GCD is just to avoid overflow
}
long q2(long x) throws Exception{
return lcm(lo2, gcd(hi2, x));
}
}
long gcd(long a, long b){return b == 0?a:gcd(b, a%b);}
long lcm(long a, long b) throws Exception{
// hold(a > 0 && b > 0);
if(a == 0 || b == 0)return 0;
return a*(b/gcd(a, b));
}
//SOLUTION END
void hold(boolean b)throws Exception{if(!b)throw new Exception("Hold right there, Sparky!");}
static boolean multipleTC = true;
FastReader in;PrintWriter out;
void run() throws Exception{
in = new FastReader();
out = new PrintWriter(System.out);
//Solution Credits: Taranpreet Singh
int T = (multipleTC)?ni():1;
pre();for(int t = 1; t<= T; t++)solve(t);
out.flush();
out.close();
}
public static void main(String[] args) throws Exception{
new ALTLG().run();
}
int bit(long n){return (n==0)?0:(1+bit(n&(n-1)));}
void p(Object o){out.print(o);}
void pn(Object o){out.println(o);}
void pni(Object o){out.println(o);out.flush();}
String n()throws Exception{return in.next();}
String nln()throws Exception{return in.nextLine();}
int ni()throws Exception{return Integer.parseInt(in.next());}
long nl()throws Exception{return Long.parseLong(in.next());}
double nd()throws Exception{return Double.parseDouble(in.next());}
class FastReader{
BufferedReader br;
StringTokenizer st;
public FastReader(){
br = new BufferedReader(new InputStreamReader(System.in));
}
public FastReader(String s) throws Exception{
br = new BufferedReader(new FileReader(s));
}
String next() throws Exception{
while (st == null || !st.hasMoreElements()){
try{
st = new StringTokenizer(br.readLine());
}catch (IOException e){
throw new Exception(e.toString());
}
}
return st.nextToken();
}
String nextLine() throws Exception{
String str = "";
try{
str = br.readLine();
}catch (IOException e){
throw new Exception(e.toString());
}
return str;
}
}
}
Feel free to share your approach. Suggestions are welcomed as always. 