Codeforces 1327A: Sum of Odd Integers

Codeforces C++ 一解.

分析

本题需要对任意的 $n$ 确认其能否表示成各不相同的正奇数之和. 标有 “math” tag 的题目往往只需要很简短的代码就可以实现. 注意到从 1 开始的前 $k$ 个奇数之和为

$$
\sum_{i=1}^{k}(2i-1)=\frac{(1+(2k-1))*k}{2}=k^2.
$$

所以很自然地, $n<k^2$ 时显然不可能表示出来. 再考虑奇偶性, 显然 $n$ 和 $k$ 的奇偶性不同时也是无法表示的.

那剩下的数字怎么办? 这里需要用到数学竞赛中经常使用的构造特例的方法: 构造下列奇数列 $1,3,5,\cdots,2(k-1)-1,r$, 其中 $r=n-1-3-5-\cdots-(2(k-1)-1)$. 首先容易得到 $n\geq k^2$ 所以 $r>2(k-1)-1$; 再者, $n$ 减去 $k-1$ 个奇数, 在 $n$ 和 $k$ 奇偶性相同时, 其结果一定是奇数. 这就说明对于其他情况, 一定存在这样的表示方式.

综上, 我们只需要对 $n$ 的大小以及 $n$ 与 $k$ 的奇偶性做判断就可以了.

代码

#include <cstdio>

using namespace std;

bool check(long long n, long long k) {
    return (n >= k * k) && (n % 2 == k % 2);
}

int main() {
    long long t, n, k;
    scanf("%lld", &t);
    for (int i = 0; i < t; ++i) {
        scanf("%lld%lld", &n, &k);
        if (check(n, k)) {
            printf("YES\n");
        } else {
            printf("NO\n");
        }
    }

    return 0;
}