Yup! My solution is also using Sparse Table and binary search
https://www.codechef.com/viewsolution/26520870
Btw some people also got AC using optimized O(n²)
3 Likes
Well maybe you need to do some optimisations. I used the iterative implementation of segtree. Also maybe change some long longs to ints, that might help.
Hey @s5960r your code gives 13 as output
for
5
1 2 3 4 1
1
2
I expect output to be 14.Can you correct me if i am wrong
I also get 13.
Can you explain why According to me all subarrays are valid except 1 which contains 3 only.Can you explain what i am missing?
@ssjgz valid subarray means the subarray which can be used to generate answer to the given equation
1 Like
What do you mean by a subarray is “valid”?
1 Like
GCD of subarray with only 4 is 4. 2 is not divisible by 4.
2 Likes
[1]
[1,2]
[1,2,3]
[1,2,3,4]
[1,2,3,4,1]
[2]
[2,3]
[2,3,4]
[2,3,4,1]
[3,4]
[3,4,1]
[4,1]
[1]
These are all “valid” subrrays, i generated them by bruteforce. and they are 13
3 Likes
Isn’t it O(N \times log^{2}(N) \times log^2(A[i]) ) ? (only the construction without the sieve)
For each of the N elements of the array you run a binary search O(log A[i]) times. Each binary search runs in O(log N \times |st|) , where |st| is the Segment tree query complexity.
The segment tree query is usually O(logN) , but also you have the complexity of the gcd function, so the total complexity of the query is O(log N \times logA[i] ).
If you use Sparse Table, complexity will be O(N \times log(N) \times log^2(A[i]) ) .
I remember using the same idea (with Sparse Table) in this problem of GYM CF : C - Collatz Conjecture and I got TLE.
Maybe there weren’t strong testcases.
1 Like
The solution is O(N \cdot \log^3 N), and passes due to weak tests.
2 Likes
I didn’t analyse the time complexity well. Nice analysis. RIP for me I guess.
can anyone help me with this :
https://www.codechef.com/viewsolution/26614356
I know my solution is very bad , but i still didn’t understand editorial :(
,
so just tell me if the question is that we have to map the gcd of all subarrays , then how we do?
ex: A = [2,4]
subarrays -
2 → gcd(2) = 2 mp[2]—>1
(2,4)->gcd(2,4) = 2 mp[2]–>2
4–>gcd(4)=4 mp[4]—>1
so map is
2–>2 times
4–>1 times
After finding gcd instead of iterating all divisors at runtime, use sieve to precompute answer for each valid K.
for(i=1;i<max;i++)
for(j=I;j<max;j+=i)
ans[j]+=freq[i]
Means my above code to store gcd is good right…
@ssrivastava990 Bro i think your GCD calculation time complexity is O(n^2) , that’s what giving you TLE
I’ll tell you my method, you basically need to reduce that O(n^2)
The question can be divided into two parts
Task 1. For all possible subarrays, find their GCD and no of times the occur i.e frequency
Task 2. like @l_returns said, use sieve method for queries. I’ll explain my answer in detail.
My Solution which i’m refering
Line No 162 to 165 => Variable Declaration
Line No 166 to 169 => I build my sparse table, that can give me GCD of any range in log(n) time
Line No 170=> I create a map which would map a GCD with its frequency
Line No 171 to 182 => THIS IS WHERE I CALCULATE GCD WITH THEIR FREQUENCY
Basically GCD if calculated from a index, will either decrease or stay constant. Hence it’s monotonic in nature, so i can use binary search.
Line No 142 to 154 => MY Binary Search function that returns the index of the position where GCD decreases
I start with any index and call it my original GCD. Now I binary search the index where it decreases. Now i use my original index and that index to calculate the increase in the frequency of that GCD, by using the difference in index.
So in nlog(n) time i calculated all possible GCD with their frequency.
So Task 1 Complete Yay!
Now coming to task #2, it’s easy
Line No 186=> I call a function, fillDp();
Line No 197 to 202 => I’m using the sieve method here, i take any GCD (say X) and i add its frequency to all multiples of that GCD, simple! You can learn more about Sieve method from internet
So for all query ‘q’ , we simply outout the dp[q].
Task 2 accomplished ! and time for AC 
Let me know if any part of solution is unclear?
1 Like
Can someone please help me understand this
“(Remember there are only at max O(log(A[i]))” this phrase. I had thought this idea thoroughly during the contest but i was thinking it as in start i will have 1 subarray, then 2 subarrays, then 3 subarrays and so on till n-1 subarrays.
Some of them will have same gcd values but how this sum reduces to nlogn from n^2
For making the gcd frequency array how we won’t take order n^2 time?
It’ means that If you have a array say
[n1,n2,n3,n4.....nn]
and you start to take total GCD from a number say n2 , then the total GCD will only decrease
and it can decrease to a maximum of log(n2) distinct values.
Now you understand? 
1 Like
How can we show the correctness of this proposition? That log(n2) part
I didn’t really proof that 
…but i knew that the changed GCD can only be equal to n2 or a divisior of n2, so it came to me somehow