数学/数论 奇偶性 -- 题解 CF1327A 【Sum of Odd Integers】

## 题面简述 > 给定 $n,k$，判断 $n$ 是否能被表示成 $k$ 个不同的正奇数之和。 ## 算法分析 首先取出前 $k$ 个奇数： $$1,3,5,7,\dots,2k-1$$ 求和： $$\sum_{i=1}^k(2i-1)=\dfrac{k(1-2k+1)}{2}=k^2$$ 得出结论：$k$ 个不同的正奇数的最小和为 $k^2$。 只要不断将最大的奇数加 $2$，我们就能构造 $k$ 个奇数使其和为 $n$。 所以当 $n-k^2\ge 0$ 且 $(n-k^2)\bmod 2=0$ 时一定有解。 当 $n-k^2<0$ 时，显然不能构造。 $k$ 个奇数相加，它的奇偶性一定和 $k$ 保持一致。 因为 $k$ 的奇偶性和 $k^2$ 一致，所以当 $(n-k^2)\bmod 2=1$ 时也不能构造。 所以“$n-k^2\ge 0$ 且 $(n-k^2)\bmod 2=0$”是有解的**充要条件**。 所以只要判断 $n$ 和 $k$ 奇偶性是否相同和 $n$ 是否 $\ge k^2$ 即可。