### shubhamgoyal__'s blog

By shubhamgoyal__, history, 3 years ago, ,

Can somebody please explain how to use the Möbius function to solve this problem. https://www.hackerrank.com/contests/w3/challenges/gcd-product

• +21

 » 3 years ago, # | ← Rev. 4 →   +23 Let f(n,m) denote the number of pairs (x, y), such that x ≤ n, y ≤ m, and gcd(x,y) = 1. WLOG, assume n ≥ mUsing inclusion exclusion,If we store an array of prefix sums of mobius function, then f(n, m) can be calculated in .Now let G(g, n, m) be the number of pairs (x, y), such that x ≤ n, y ≤ m, and gcd(x, y) = g.Clearly, . There are clearly different values of this for all the g'sOur required answer is . Considering the different ranges in which G(g, n, m) is same, this can be calculated in O(n).
•  » » 3 years ago, # ^ |   +3 Thanks for the nice explanation.
 » 2 years ago, # | ← Rev. 2 →   +20 I solved it little differently. After the step ans = Πg = 1pow(g, |{(p, q): gcd(p, q) = g}|)Now I define a function f, such that for any prime p, f(pa) = p else f(n) = 1. It must be noted that g = Πd|gf(d), Now If I substitute this expression in above expression and rearrange the multiplication we get ans = Πx = 1pow(f(x), |{(p, q): gcd(p, q)%x = 0}|)which reduces to ans = Πx = 1pow(f(x), (n / i)(m / i)). Now this is very simple to evaluate.