×

# GQR - Editorial

Div1, Div2
Practice

Author: Misha Chorniy
Tester: Lewin Gan

Medium

# PREREQUISITES:

Familiarity with GCD, Dynamic Programming

# PROBLEM:

You are given a sequence $A$ with $N$ elements and $Q$ queries on this sequence. In each query, you are given two indices $L$ and $R$; you should compute the maximum value of the greatest common divisor (GCD) of two elements $A_x$, $A_y$ satisfying $L \le x < y \le R$.

# EXPLANATION:

We will try to pre-compute the answers for all the possible query ranges. For the same purpose create two two-dimensional array $TEMP[N][N]$ and $ANS[N][N]$, where $N=10005$. We will define $ANS[L][R] = max(TEMP[x][y])$ ∀ $L \le x < y \le R$.

Observation: Let's take a look at multiple of any particular numbers $D$. Say the multiples of $D$ in the array are located at $i_1,i_2,i_3,..i_k$. Now, any query range which contains atleast two of the above index will have answer $\ge D$ (Why?). If we update $TEMP[i_j][i_{j+1}] = max(TEMP[i_j][i_{j+1}],D)$ ∀ $j < k$, and re-compute $ANS$ array, we can see it will cover all the required query ranges that needs to be updated.

We will try to build our solution using the above observation. Iterate over each of the numbers in the array, find their respective divisors in $O(\sqrt{A[i]})$. Corresponding to every divisor, find the right most index $j < i$ where multiple of this divisor has appeared. You can use another array to ease this process. After finding such $j$ you just need to update $TEMP[j][i]=max(TEMP[j][i],\text{corresponding divisor})$.

Once you have iterated over all the numbers, compute $ANS[x][y]$ ∀ $1 \le x < y \le N$. You can have a look at pseudo-code for the same,

for i=1...N-1:
ANS[i][i+1]=TEMP[i][i+1]
for l=3...N:
for i=1...(N-l+1):
j = i+l-1
ANS[i][j] = max(ANS[i+1][j],ANS[i][j-1])
ANS[i][j] = max(ANS[i][j],TEMP[i][j])

You can answer every query in $O(1)$ now.

# Time Complexity:

$O(N^2+Q)$.

# AUTHOR'S AND TESTER'S SOLUTIONS

This question is marked "community wiki".

306719
accept rate: 7%

19.8k350498541

 0 Constraints were too tight. Even testers code gave tle: https://www.codechef.com/submit/complete/18017154 answered 01 Apr '18, 23:37 2.5k●4●21 accept rate: 17% 1 It isn't tester's solution. It's kind of very fast O(N^2 log A) solutions. Here is the tester's solution: https://pastebin.com/0NMGeUtw (01 Apr '18, 23:43) mgch6★
 0 If you understood the concept of using the insight that if gcd(a, b) = g, then it means that a and b are multiples of g, here is a problem from HackerRank where you can practice the same concept. answered 02 Apr '18, 12:33 58●5 accept rate: 5%
 0 "If we update $TEMP[ij][ij+1] = max(TEMP[ij][ij+1], D)$ ∀j
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×15,852
×2,658
×2,214
×321
×47
×5

question asked: 31 Mar '18, 19:11

question was seen: 2,046 times

last updated: 10 Apr '18, 13:34