The official editorial of the Half Sequence says

**This**

**Reason they give**

But, what is the proof behind it? I mean what is the intution behind saying this? Can someone give a formal proof for it.

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

1 | tourist | 3707 |

2 | Benq | 3672 |

3 | ksun48 | 3575 |

4 | Radewoosh | 3562 |

5 | Miracle03 | 3480 |

6 | maroonrk | 3406 |

7 | ecnerwala | 3400 |

8 | peehs_moorhsum | 3384 |

9 | sunset | 3338 |

10 | Um_nik | 3320 |

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

1 | 1-gon | 208 |

2 | Um_nik | 197 |

3 | YouKn0wWho | 192 |

4 | Errichto | 182 |

5 | sus | 181 |

6 | awoo | 180 |

7 | tourist | 175 |

8 | -is-this-fft- | 171 |

8 | SecondThread | 171 |

10 | Ashishgup | 170 |

The official editorial of the Half Sequence says

For N > 18 (practically, even 16), remove all odd numbers from the input. If we have atleast (N+1)/2 elements remaining and if their GCD is 1 then we have a solution.

Observe that any single number (<=10^9) can be made up of atmost 9 distinct prime numbers. This means that if GCD([B_0, B_1,..., B_N]) = 1, then there must exist atleast one subset of length at most 9 whose elements have GCD=1.

But, what is the proof behind it? I mean what is the intution behind saying this? Can someone give a formal proof for it.

↑

↓

Codeforces (c) Copyright 2010-2021 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Oct/25/2021 19:58:08 (h2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|

Auto comment: topic has been updated by aopo (previous revision, new revision, compare).I mean how having atmost 9 distinct prime factors allows us to directly say YES/NO even without brute forcing for larger N?

Pick any number A. If (N+1)/2 >= 10 then for every prime p that divides A you can just pick one number that is not divisible by p. These <=10 numbers already have GCD=1 and you can pick any other numbers to make it (N+1)/2 total.

Exactly Same Problem , but with smaller constraints on a[i]:(https://codeforces.com/problemset/problem/1043/F)

If you have a subset $$$S$$$ of size less than $$$ceil((N+1)/2)$$$ with $$$\gcd(S)=1$$$, you can insert to it any $$$ceil((N+1)/2)-|S|$$$ elements and it'll still satisfy the gcd condition. So your goal is to find any subset of size $$$\le ceil((N+1)/2)$$$ with $$$\gcd = 1$$$.

Fix any element $$$x$$$ in $$$B$$$ which must be included in $$$S$$$. $$$x$$$ can have at most 9 distinct prime factors. Let them be $$$p_1, \cdots, p_k, k \le 9$$$. Since $$$\gcd(B)=1$$$, for each $$$p_i$$$, $$$B$$$ must have an element $$$b_i$$$ which is not divisible by $$$p_i$$$ ($$$b_i$$$s can be equal). Then just set $$$S=\lbrace x, b_1, \cdots, b_k \rbrace$$$, and we must have $$$\gcd(S)=1$$$ since $$$\gcd(S)$$$ divides $$$x$$$ and none of the $$$p_i$$$ divides it. This set is enough to determine that the answer is YES if $$$|S| \le k+1 \le ceil((N+1)/2)$$$. Since $$$k \le 9$$$, this inequality always hold if $$$N \ge 18$$$.

Ok, so i guess using this fact/understanding we can even find 1 such possible susbset.