Part1 定理内容
\(n\) 为整数，对于任意 \(2n-1\) 个整数，总可以选出 \(n\) 个数使得它们和为 \(n\) 的倍数。
Part2 定理证明
考虑证明如下两个引理：
-
引理 1：对于任意 \(n,m\)，若它们都满足定理，那么 \(nm\) 也成立。
证明：
我们需要证明在 \(2nm-1\) 个数里能够选出 \(nm\) 个数和为 \(nm\) 的倍数。
考虑做 \(2m-1\) 次：在剩余的数中选出 \(n\) 个和为 \(n\) 的倍数的数。
在最后一次选择时还剩 \(2n-1\)，刚好够用。
此时得到 \(2m-1\) 组数，每组是和为 \(n\) 的倍数的 \(n\) 个数。
在它们中选出和为 \(m\) 的倍数的 \(m\) 组即可得到方案。
证毕。
-
引理 2：对于任意素数 \(n\)，定理都成立。
证明：
若 \(2n-1\) 个数中有一个的出现次数不少于 \(n\)，则直接取 \(n\) 个这种数即可。
若 \(2n-1\) 数中没有这种数即没有绝对众数，那么考虑每次取出现次数最大和次大的两种数，并将它们分为一组，执行这个操作 \(n-1\) 次，直到剩下一个数，把它单独分为一组。
此时得到了 \(n\) 个组，考虑先在方案里选择每个组里的第一个数。
考虑调整，即对于 \(n-1\) 个二元组 \(\{(x,y)\}\) 而言，可以选择对总和的变化量贡献 \(0\) 或 \(y-x\)，因为没有绝对众数，\(y-x \ne 0\)，下文记 \(\bigtriangleup=y-x\)。
考虑从前往后扫所有可以变化的 \(n-1\) 的组，记当前通过调整可以得到的模 \(n\) 意义下的和是集合 \(S\)，初始 \(S\) 中只有当所有集合都选择第一个数的和。
考虑一个二元组时，相当于是 \(S \to \{x\ |\ x \in S \or (x-\bigtriangleup) \bmod{n} \in S\}\)。
考虑说明每考虑一个新的二元组的变化量，\(|S|\) 都会增加。
反证，若任意 \(x \in S\) 都有 \((x+\bigtriangleup) \bmod{n} \in S\)，此时 \(|S|\) 不会增加，试说明这种情况不存在？
考虑取任一 \(x \in S\)，取 \(T_k=(x+k\bigtriangleup) \bmod{n}\)。则因 \(\gcd(x,n)=1\)，有 \(|\{T\}|=n\)。容易说明当 \(|S| \ne n\) 必然存在 \(T_k \in S \and T_{k+1} \not\in S\)。
因此经过 \(n-1\) 次以后 \(|S|=n\)，显然包含 \(0\)。
证毕。
显然此时通过质因数分解的理论可以推广到任意整数。
Part3 例题
CF1798F
有 \(n+1\) 个数，其中 \(n\) 个数给定。你需要将它们分为 \(k\) 组，每组分别有 \(s_1,s_2,...,s_k\) 个数，其中 \(s_1+s_2+...+s_k=n+1\)。你需要使得每组数的和为相应 \(s\) 的倍数。请你给第 \(n+1\) 个数分配数值并输出一种方案。
\(k-1 \leq n \leq 200\)。
直接应用定理即可。考虑按照 \(s\) 从小到大确定方案，只有在 \(s\) 最大的那个组的时候会有可能无解，此时用那个未确定的值来调整即可。