FUZZYLIN - Editorial

How can we show the correctness of this proposition? That log(n2) part

I didn’t really proof that :rofl:…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)

@ssrivastava990 Consider the following case:
N = 10^5 and each A[i] = 3
Your solution is O(n^2).

So plz tell me how can I store all gcd frequency of all subarray less than o( n^2)

@ssrivastava990 by using binary search for every i from 0 to n-1

bhai…just tell me why did you used sparse table and how did you used that binary search…bhai hindi me hi samjha :joy: 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?

This problem is almost same to this problem on Codeforces
problem.

2 Likes

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