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