朝鲜时蔬 的一些力所能及的证明
题意
(~~~~) 包含 (1sim n) 的所有元素的集合，有多少个 (m) 阶子集，这个 (m) 阶子集的和能被最多该集合的 (k) 阶子集和整除。
(~~~~) (1leq kleq mleq nleq 10^{12},1leq mleq 4)
题解
(m=1,k=1)
(~~~~) 任选集合一定成立，故答案为 (n) .
(m=2,k=1)
答案
(~~~~) 设答案的 (m) 阶子集为 ({a,b}(a<b)) ，则必定有 (a|(a+b) Rightarrow a|b) ，因此枚举 (a) ，得到：
(~~~~) 整除分块即可。
证明
(~~~~) 证明不可能存在 (a|(a+b)) 且 (b|(a+b)) ：
(~~~~) 你看样例解释里面不存在这种情况
- 若 (a ot|~b) ，则显然不成立；
- 否则，设 (b=ka,kin mathcal{Z^*}) ，则应满足 (a|k+1 land ka|k+1) ，两式结合有 (k|1)，即 (k=1)，不满足 (a<b) 的限制。
(m=2,k=2)
答案
(~~~~) 显然选择所有集合均可，答案为 (egin{pmatrix} n\2 end{pmatrix}) .
(m=3,k=1)
答案
(~~~~)(m=3,k=1) 的最优集合为 ({k,2k,3k}) ，故答案为 (lfloor dfrac{n}{3} floor).
证明
(~~~~) 证明其最优集合的形式：
(~~~~) 设 ({ak,bk,ck}(a<b<c)) 为最优集合形式 ，由已知的形式：
(~~~~) 稍微化一下：
(~~~~) 设：(ck=a+b Rightarrow c=dfrac{a+b}{k} (k in mathcal{Z^*})) ，由 (a<b<c) 可知 (k=1)
(~~~~) 故：
(~~~~) 设：(pa=2b Rightarrow a=dfrac{2b}{p} (p in mathcal{Z^*})) ，则代入: (b|dfrac{4b}{p}) ，(p=1,2,4) ，此时分别有 (a=2b,a=b,a=dfrac{1}{2}b) ，结合 (a<b<c) 的条件，则只有 (a=dfrac{1}{2}b) 满足条件。再代入 (c=a+b)，此时有 (a:b:c=1:2:3) .
(m=3,k=2)
答案
(~~~~) 设：最优集合为 ({a,b,c}(a<b<c)) ，则最优集合只有 ((a+b)|(a+b+c) Rightarrow (a+b)|c) ，枚举 (a+b) ，同时再算上拆分方案即可：
(~~~~) 整除分块即可。
(m=3,k=3)
答案
(~~~~) 任选集合一定成立，答案为 (egin{pmatrix} n\3 end{pmatrix}) .