CF Kate and imperfection

题目来源:Codeforces Round #632 (Div. 2) 题目链接:F. Kate and imperfection 大致题意 给出一个数n,S为从1到n的集合,寻找长度为2,3,4...一直到长度为n的子集中任意两个数的最大公约数的最小值。举个例子有一个集合{2,4,6,9},它的值就应该为6和9的最大公约数3,而它的长度为2的子集的最大公约数的最小值可以选子集{4,9},这样就是1。 思路 强行找的话肯定会超时,因此我们先研究一下这个规律。假设n等于10的时候,长度为2的子集 肯定选最大公约数为1的两个数,任选10一下的两个素数组成的子集,答案为1;长度为3的子集依然选3个素数