http://www.1point3acres.com/bbs/thread-180481-1-1.html
从1到n选择尽可能多的数，使得任意两个数不为倍数关系，问你最大能取多少个数（或者如题目所说的，至少多少个必然存在冲突）
第一反应也是找primes，结果举了个1~10的例子检验就发现不对了。。。
把1－n数字列出来，有整除关系的数之间加一条边，问题就转换成为找最大的集合使得集合里的数互相没有边，答案就是集合里数的个数＋1，枚举几个n之后，我觉的答案就是n/2+1，因为n是偶数，所以[n/2 + 1, n]之间不能互相整除，n/2之前的数必然能整除[n/2 + 1, n]之间的某个数，因为将其乘2得到的结果必然在[n / 2 + 1, n]直接，所以我认为答案应该就是n/2 + 1
我觉得证明不难啊，用contradiction证，假设大于（n+1）/2，那么肯定有一些数落在（0，n/2）,假设有x个，那么这些数的2倍就不可以出现在（n/2，n）中，所以（n/2,n）至多有n/2-x个，所以总数至多有（n+1）/2个，得出矛盾。
大概是这个意思，边界我就没细分析了
so 直接return n/2+1（感觉是这个），那还写啥...就像n lines divide plane那个题，直接return 1+(1+n)*n/2不就可以...But那个lz跑test case跑不过...?
第一反应也是找primes，结果举了个1~10的例子检验就发现不对了。。。
把1－n数字列出来，有整除关系的数之间加一条边，问题就转换成为找最大的集合使得集合里的数互相没有边，答案就是集合里数的个数＋1，枚举几个n之后，我觉的答案就是n/2+1，因为n是偶数，所以[n/2 + 1, n]之间不能互相整除，n/2之前的数必然能整除[n/2 + 1, n]之间的某个数，因为将其乘2得到的结果必然在[n / 2 + 1, n]直接，所以我认为答案应该就是n/2 + 1
我觉得证明不难啊，用contradiction证，假设大于（n+1）/2，那么肯定有一些数落在（0，n/2）,假设有x个，那么这些数的2倍就不可以出现在（n/2，n）中，所以（n/2,n）至多有n/2-x个，所以总数至多有（n+1）/2个，得出矛盾。
大概是这个意思，边界我就没细分析了
so 直接return n/2+1（感觉是这个），那还写啥...就像n lines divide plane那个题，直接return 1+(1+n)*n/2不就可以...But那个lz跑test case跑不过...?
