1034A - Enlarge GCD There has been no editorial after the contest . so can someone help me to solve this problem ?

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

1 | tourist | 3557 |

2 | Radewoosh | 3468 |

3 | Um_nik | 3429 |

4 | Petr | 3354 |

5 | Benq | 3286 |

6 | mnbvmar | 3280 |

7 | LHiC | 3276 |

8 | wxhtxdy | 3258 |

9 | ecnerwala | 3214 |

10 | yutaka1999 | 3190 |

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

1 | Errichto | 191 |

2 | Radewoosh | 180 |

3 | tourist | 173 |

4 | Vovuh | 166 |

4 | antontrygubO_o | 166 |

6 | PikMike | 164 |

7 | rng_58 | 160 |

8 | majk | 156 |

9 | Um_nik | 155 |

9 | 300iq | 155 |

1034A - Enlarge GCD There has been no editorial after the contest . so can someone help me to solve this problem ?

↑

↓

Codeforces (c) Copyright 2010-2019 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Oct/22/2019 20:54:30 (h2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|

Suppose the gcd of the initial array is x. Divide every element by x. Now you simply find the largest subset which has gcd > 1.

43212157 I have tried this idea but i got a TLE . I am wondering if it can be improved

your gcd implementation is bugged.try this

You could also use the __gcd(a,b) function in the bits/stdc++.h library

how can we find the largest subset for which gcd>1 ?

For the remaining elements in our group, we have some prime p that divides them all, since otherwise their gcd would be one. Therefore, the prime is also ≤ 1.5 * 10

^{7}.You can just find all primes below that bound, and then count how many different numbers that prime appears in. To do this, just factor every a_i, and increment the primes's counters that appear in its factorization.

But how can we prove ,new gcd is greater than old gcd

Because we divided all elements with old gcd, old gcd is 1. New gcd is >= p, with the prime we choose, so it is greater than the old gcd.

I am not able to get this, can you explain a bit more or attach any link from where i can understand this.

In their test no 4 , their input is: 2 1 7 with ans 1 which means 1 removal but according to this doesn't the answer become n-(no of occurrences of maximum element of the array)