其实我用了一种操蛋的贪心试了一下，所有的cf测试数据里只有一组会错。。但是还没有搞明白为什么错了，也没有办法再继续证明正确性，所以还是放弃了去看tutorial，发现果然没思路就是dp。。。
然后这又不是一个正常的dp，甚至可以说不算是dp吧。。要从一堆数字里选出来一个集合使得gcd为1。确实，涉及到集合就很难操作。但是可以发现，如果这个集合存在，他的size是很小的，这里可以作为一个突破点去想。如果考虑枚举集合的大小，是否能有简单的计算方法。现在需要求的东西可以转化为，是否存在至少一个集合使得他的size为i然后gcd为1，当然这个也不好直接算，但如果再加一维，再枚举gcd，看看会不会有进展：这时候要求的转化为，是否存在至少一个集合，size为i，gcd为j。可以设一个dp[i][j]表示这种集合的数量，然后尝试是否可以递推。这时候可以发现这i个数字一定是从j的倍数里选出来的，所有的选法有C(cntj,i)种，其中cntj是原数列中j的倍数的数量。而这些里面又有一些不符合要求的，是因为他们的gcd=k*j，然后可以发现这些不符合要求的数量就是dp[i][k*j]，这就实现了从大问题往小问题推的转移了。。。然后就只剩下边界的问题了，这个边界也很有意思：因为只考虑k*j<=max(ai)的gcd，所以大于的就是0就可以了