Problem Link (Contest)  https://www.codechef.com/LOCAUG17/problems/GTREE I tried to solve the above problem from LoC AUG 2017 and wrote a brute force solution (by doing a DFS from each node in its subtree) that fetched 30 pts but couldn't come up with an approach to solve this problem completely. Can someone explain how to solve this problem? asked 29 Aug '17, 02:14

I have a better approach. The key problem is that: Given several integers, with integer $x$ appears $c_x$ times, and some fixed integer $m$. It is asked that how many integers that are coprime to $m$, i.e. $$ \sum_{i=1}^n c_i [ \gcd (i, m) = 1 ]. $$ By Mobius inversion, we can get that $$ \sum_{i=1}^n c_i [ \gcd (i, m) = 1 ] = \sum_{dm} \mu(d) \sum_{i=1}^{\lfloor n/d \rfloor} c_{id}. $$ Here we use some technique when we DFS the tree, for each vertex $v$, and every $val_v$'s divisor $d$, maintain $$ s(d) = \sum_{i=1}^{\lfloor n/d \rfloor} c_{id}, $$ and thus we can get $s(d)$ in $O(1)$ each time. As above, an $O(n \max_{k} \sigma(k))$ algorithm is exhibited, where $\sigma(k)$ means the number of $k$'s divisors. For more details, please see my code. answered 09 Sep '17, 07:39
1
@liouzhou_101 $s(d)$ appears to be
(15 Sep '17, 20:21)

$$ \begin{aligned} & \quad \sum_{i=1}^n c_i [ \gcd(i, m) = 1 ] \\ & = \sum_{i=1}^n c_i \epsilon(\gcd(i, m)) \\ & = \sum_{i=1}^n c_i \sum_{d\gcd(i, m)} \mu(d) \\ & = \sum_{i=1}^n c_i \sum_{dm} \mu(d) [di] \\ & = \sum_{dm} \mu(d) \sum_{i=1}^n c_i [di] \\ & = \sum_{dm} \mu(d) \sum_{i=1}^{\lfloor n/d \rfloor} c_{id} \\ \end{aligned} $$ answered 15 Sep '17, 08:39

@liouzhou_101 How did you convert ∑dmμ(d)∑i=1⌊n/d⌋cid I have already this and this but not able to figure out how you converted to mobius inversion. Can you please explain that formula answered 15 Sep '17, 00:11

I didnt give any submissions on the problem... but I can write what i think is a correct solution. So, first... flatten the tree into an array. So now the problem is to solve range queries where each query returns the number of non coprime numbers. First, compress the numbers so that they contain its prime factors only once. for example, 72 = 2 * 2 * 2 * 3 * 3 Write it as 2 * 3  meaning that every unique prime factor is taken only once. So you can easily show that a number will contain at most 6 factors in this form. for that just take the product of the first 7 unique prime numbers and that will exceed 1e5, the max size of the number. Now, maintain list of all the possible factors and their multiples that are present. Now this may seem to be N^2 as you are maintaining 1e5 sized array of vectors, but each number can have atmost 2^6 factors, so in all there can be at most 2^6 * N elements. Now given a range, basically do a principle of inclusion and exclusion type thing, and binary search for the numbers present in the range, using the aforementioned lists that have been made. The whole factorization can be done in NlogN time using the smallest prime factor seiving technique, and the overall complexity should be about 2^6 * log^2 N per query approx.( this may be actually logN, i forgot :p ). This should work within the given time limit. I hope this was a correct solution. answered 29 Aug '17, 17:28

@rajashri_basu can you please explain the last paragraph a little more? answered 29 Aug '17, 22:40

How do we apply binary search in your last part , like what is the property that is monotonic here , I understood the property of inclusion and exclusion like suppose if our curr_subtree node has {2,3,5} as it's unique prime divisor's then we will use inclusion and exclusion principle to find like how many numbers are divisible in that range by atleast one of the numbers from our given list like we will find how_many_divisible_by(2)+how_many_divisible_by(3)+how_many_divisible_by(5)how_many_divisible_by(2 3)how_many_divisible_by(2 5)how_many_divisible_by(3 5)+how_many_divisible_by(2 3* 5) in that range and u are saying that we can find the value of a how_many_divisible_by(x) by using binary search in that range but i don't understand how to apply binary search . answered 05 Sep '17, 23:14

There are do not need array and binary search. Simple dfs and use array with number of multiples present in upper nodes. answered 08 Sep '17, 20:20

@liouzhou_101 ♦♦ Can you explain how you converted the problem to: "Given several integers, with integer x appears cx times, and some fixed integer m. It is asked that how many integers that are coprime to m" answered 09 Sep '17, 16:26

For every vertex $x$ in the tree, it is asked that how many vertices $y$ in the subtree of $x$ such that $\gcd (val_y, val_x) > 1$. It can be converted to that how many vertices $y$ in the subtree of $x$ such that $\gcd (val_y, val_x) = 1$ (The original problem's complement.), where $val_x$ is the $m$, and $val_y$ are the integers $x$. answered 09 Sep '17, 21:41

I checked a few solutions and they seem to be using the Möbius function, which I don't know about. I'm reading up on it and if I am able to understand the solution I'll explain it here.