×

# How to solve GTREE - "TREE GCD" ?

 2 5 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 1.1k●5 accept rate: 17% 2 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. (29 Aug '17, 22:46) meooow ♦6★

 9 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 co-prime 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_{d|m} \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 682●2●3●13 accept rate: 12% 1 @liouzhou_101 $s(d)$ appears to be cnt[d] in your code, but $s(d)$ is the number of times any multiple of $d$ occurs whereas cnt[d] is just the number of times $d$ appears. Am I getting something wrong? (15 Sep '17, 20:21) meooow ♦6★
 2 @skyhavoc \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_{d|m} \mu(d) [d|i] \\ & = \sum_{d|m} \mu(d) \sum_{i=1}^n c_i [d|i] \\ & = \sum_{d|m} \mu(d) \sum_{i=1}^{\lfloor n/d \rfloor} c_{id} \\ \end{aligned} answered 15 Sep '17, 08:39 682●2●3●13 accept rate: 12%
 1 @liouzhou_101 How did you convert ∑d|mμ(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 4★skyhavoc 161●6 accept rate: 0%
 1 cnt[d] is to calculate the number of times any multiples of $d$ occurs, however, it is not that itself. In my code: void dfs(int x, int pre) { size[x] = 1; ans[x] = 0; for (auto d : divisor[a[x]]) { ++ cnt[d]; ans[x] -= u[d]*cnt[d]; } for (auto y : v[x]) { if (y == pre) continue; dfs(y, x); size[x] += size[y]; } for (auto d : divisor[a[x]]) ans[x] += u[d]*cnt[d]; ans[x] = size[x]-1-ans[x]; } Note that ans[x] = ∑ u[d]*( (cnt[d] after dfs the subtree of x) - (cnt[d] before dfs the subtree of x) ), which implies that ( (cnt[d] after dfs the subtree of x) - (cnt[d] before dfs the subtree of x) ) is to calculate s(d). Note that when we run dfs(x, pre), before looping "for (auto y : v[x])", for each a[x]'s divisor d, what we do is "cnt[d] ++". And the difference of cnt[d] before and after the loop is exactly what we want to calculate, i.e. s(d). If still confused, think of the DFS order of a tree and implement it by hand in order to understand what the procedure exactly does. answered 16 Sep '17, 09:38 682●2●3●13 accept rate: 12% 1 I did understand why you were subtracting first and adding up after the children were visited, because of the DFS order, but I guess I didn't fully grasp what was happening. I thought about it a bit more and it's clear to me now, thanks! (16 Sep '17, 13:28) meooow ♦6★
 0 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 co-prime 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 628●8 accept rate: 10% i had similar idea but stuck at the inclusion and exclusion thing..(: (29 Aug '17, 21:42)
 0 @rajashri_basu can you please explain the last paragraph a little more? answered 29 Aug '17, 22:40 2★pk301 627●10 accept rate: 16%
 0 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 1●1 accept rate: 0%
 0 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 126●4 accept rate: 5%
 0 @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 co-prime to m" answered 09 Sep '17, 16:26 0 accept rate: 0%
 0 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 682●2●3●13 accept rate: 12%
 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:

×2,738
×2,657
×711
×321
×65

question asked: 29 Aug '17, 02:14

question was seen: 1,545 times

last updated: 16 Sep '17, 13:28