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

jijidawang · 2020-03-24 19:11:56 · 题解

题面简述

给定 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^2$ 一致，所以当 $(n-k^2)\bmod 2=1$ 时也不能构造。所以“$n-k^2\ge 0$ 且 $(n-k^2)\bmod 2=0$”是有解的**充要条件**。所以只要判断 $n$ 和 $k$ 奇偶性是否相同和 $n$ 是否 $\ge k^2$ 即可。