问题描述
数字王国开学了，它们也和我们人类一样有开学前的军训，现在一共有 nn 名学生，每个学生有自己的一个名字 aiai（数字王国里的名字就是一个正整数，注意学生们可能出现重名的情况），此时叛逆教官来看了之后感觉十分别扭，决定将学生重新分队。
排队规则为：将学生分成若干队，每队里面至少一个学生，且每队里面学生的名字不能出现倍数关系（注意名字相同也算是倍数关系）。
现在请你帮忙算算最少可以分成几队？
例：有 44 名学生 (2,3,4,4)(2,3,4,4)，最少可以分成 (2,3)(2,3)、(4)(4)、(4)(4) 共 33 队。
输入格式
第一行包含一个正整数 nn，表示学生数量。
第二行包含 nn 个由空格隔开的整数，第 ii 个整数表示第 ii 个学生的名字 aiai。
输出格式
输出共 11 行，包含一个整数，表示最少可以分成几队。
样例输入
4
2 3 4 4
样例输出
3
评测数据规模
对于所有评测数据，1≤n≤101≤n≤10，1≤ai≤1051≤ai≤105。
感觉和枚举子集很像。直接暴力
def check(n, grou):for i in grou:if i % n == 0 or n % i == 0:return Falsereturn Truedef find(deep, n):if deep == n: # 当到达规定的深度时（就是找遍了所有的学生）global ans # 全局变量ans = min(ans, len(num))# 找到最小的方案数（现在的方案数和之前存储在ans的最小方案数比较）return if len(num) > ans: # 剪枝，如果此时的方案数已经比之前的大return for epoch in num: # 遍历存储在num里的分组if check(student[deep], epoch): # 判断该学生可不可以加入该组epoch.append(student[deep]) # 如果可以，加入find(deep+1, n)# 考虑下一个学生该加入哪一组epoch.pop()# 退出num.append([student[deep]]) # 如果有学生不能加入任何一组，就一个人一组find(deep+1, n)num.pop()if __name__ == "__main__":ans = float("inf") # 无限大的数n = int(input()) # 输入student = list(map(int, input().split()))num = [] # 用来存储所有方案find(0, n)print(ans)
