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
I had a similar approach but got a tle could you help.
https://www.codechef.com/viewsolution/26366721
@kartikey_25 Whats the complexity of your count function? I mean what’s the time complexity per query?
The editorial said:
Assuming 1-based indexing. Let’s say we are making an array t[] of length i, where t[j] = GCD(A[i], A[i - 1], ... A[i - j + 1]). In other words, t[j] equals GCD of the last j elements in the prefix ending at A[i]. How many distinct values can there be in t[]?
We have
t[1] = A[i],
t[j] = GCD(t[j - 1], A[i - j + 1]) = \frac{t[j - 1]}{k} with k being a factor of t[j-1].
This shows that t[] is decreasing and since at each succession there is a division, there are at most O(log(A[i])) distinct values in t[].
1 Like
Haven’t checked that. If it’s O(n^2*log(n)) then change it to O(n*log^3(n)) at least or O(n*log^2(n))
The space complexity can be optimized to O(n + log n)
So plz tell me how can I store all gcd frequency of all subarray less than o( n^2)
bhai…just tell me why did you used sparse table and how did you used that binary search…bhai hindi me hi samjha 
zada samajh me aaega.what i did was for every subarray i used to find the gcd and then mark it in the seive so finding gcd for each subarray took o(n^2logn) time how did you reduced it using sparse table and binary search that i want to know… @s5960r
The third line contains in Explanation contains " if and only if" . Is that correct or Should that be only “if”
what’s the purpose of binary search here?
To find every point where the GCD changes value.
Can someone tell me how to prove this?
I can prove it in two ways
1)
Smallest factor of any number is 2.
We can divide a number till it is not “1”.
Dividing by a number \gt 2 will make it “1” faster than dividing it by 2.
Because \frac {x}{2} \gt \frac{x}{k} where k \gt 2
Hence worst case is when number is power of 2.
2^x = a[i]
x=log_2(a[i])
Hence we can divide a number at most log_2(number) times even in worst case.
2)
Let a[i] = p_1^{k_1} * p_2^{k_2} * ... *p_N^{k_N}
Where p_1,p_2,…,p_N are prime factors of a[i] and k_1,k_2,…,k_N are integers greater than 0.
and p_1<p_2<p_3 <.... <pN
a[i] = p_1^{k_1} * p_2^{k_2} * ... *p_N^{k_N}
\hspace{ 6mm} \ge p_1^{k_1+k_2+...+k_N}
We can divide it for at most k_1+ k_2+...+k_N times.
Therefore,
log_2(a[i]) \ge log_{p_1}(a[i]) \ge k_1+ k_2+...+k_N , since p_1 \ge 2 .
Hence proved.
1 Like