### aopo's blog

By aopo, history, 5 weeks ago,

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.

• +11

 » 5 weeks ago, # |   0 Auto comment: topic has been updated by aopo (previous revision, new revision, compare).
 » 5 weeks ago, # |   0 I mean how having atmost 9 distinct prime factors allows us to directly say YES/NO even without brute forcing for larger N?
 » 5 weeks ago, # |   +4 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.
 » 5 weeks ago, # |   0 Exactly Same Problem , but with smaller constraints on a[i]:(https://codeforces.com/problemset/problem/1043/F)
 » 5 weeks ago, # | ← Rev. 5 →   +15 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$.
•  » » 5 weeks ago, # ^ |   0 Ok, so i guess using this fact/understanding we can even find 1 such possible susbset.