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

# | User | Rating |
---|---|---|

1 | tourist | 3556 |

2 | wxhtxdy | 3520 |

3 | Radewoosh | 3409 |

4 | Benq | 3368 |

5 | mnbvmar | 3280 |

6 | ecnerwala | 3278 |

7 | LHiC | 3276 |

8 | sunset | 3264 |

9 | maroonrk | 3159 |

10 | TLE | 3145 |

# | User | Contrib. |
---|---|---|

1 | Errichto | 189 |

2 | Radewoosh | 177 |

3 | tourist | 173 |

4 | antontrygubO_o | 172 |

5 | PikMike | 166 |

5 | Vovuh | 166 |

7 | rng_58 | 158 |

8 | majk | 156 |

9 | farmersrice | 153 |

9 | Um_nik | 153 |

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

↑

↓

Codeforces (c) Copyright 2010-2019 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Dec/08/2019 23:05:03 (h1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|

Let f(n,m) denote the number of pairs (

x,y), such thatx≤n,y≤m, and gcd(x,y) = 1. WLOG, assumen≥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 thatx≤n,y≤m, andgcd(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 inO(n).Thanks for the nice explanation.

I solved it little differently. After the step

ans= Π_{g = 1}pow(g, |{(p,q):gcd(p,q) =g}|)Now I define a function f, such that for any prime

p,f(p^{a}) =pelsef(n) = 1. It must be noted thatg= Π_{d|g}f(d), Now If I substitute this expression in above expression and rearrange the multiplication we get

ans= Π_{x = 1}pow(f(x), |{(p,q):gcd(p,q)%x= 0}|)which reduces to

ans= Π_{x = 1}pow(f(x), (n/i)(m/i)). Now this is very simple to evaluate.