I was trying to solve this problem in Egyptian ECPC but I couldn't. Can anyone give me a hint ?

someone who already solved it said that he use disjoint set but I couldn't handle it using disjoint set .

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

1 | tourist | 3434 |

2 | fateice | 3337 |

3 | Um_nik | 3292 |

4 | OO0OOO00O0OOO0O0…O | 3280 |

5 | Syloviaely | 3274 |

6 | Petr | 3223 |

7 | Swistakk | 3105 |

8 | mnbvmar | 3096 |

9 | yosupo | 3091 |

10 | dotorya | 3081 |

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

1 | rng_58 | 163 |

2 | tourist | 160 |

3 | csacademy | 152 |

4 | Petr | 151 |

5 | Swistakk | 148 |

6 | Um_nik | 144 |

7 | Nickolas | 142 |

7 | Vovuh | 142 |

9 | BledDest | 138 |

9 | PikMike | 138 |

9 | matthew99 | 138 |

I was trying to solve this problem in Egyptian ECPC but I couldn't. Can anyone give me a hint ?

someone who already solved it said that he use disjoint set but I couldn't handle it using disjoint set .

↑

↓

Codeforces (c) Copyright 2010-2018 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Jul/23/2018 20:31:47 (d1).

Desktop version, switch to mobile version.

User lists

Name |
---|

The problem is asking for the maximum spanning tree of the graph where the edge costs between any two numbers in the array is their gcd.

SolutionIterate of all possible gcd's from largest to smallest and consider them your edge costs. At any point you can union all numbers which are divisible by this gcd as long as they weren't connected earlier.

If you process it correctly, it's fast enough.

My solution to help you understand the idea better : https://ideone.com/Vbkhnw

thank you i really appreciate your help