利用 Python 解决 “奇数之和” 问题

一、问题描述

在这个问题场景中，有着特定的时间和内存限制，每次测试时间限制为 2 秒，每个测试的内存限制为 256 MB。我们会获得两个整数 n 和 k，任务是判断 n 是否可以表示为 k 个不同的正奇数（不能被 2 整除的整数）之和，并且需要对 t 个独立的测试用例进行这样的判断操作。

输入要求

输入的第一行包含一个整数 t（满足 1≤t≤105），它代表着测试用例的数量。接下来的 t 行用于描述具体的测试用例，每一行包含两个整数 n 和 k（满足 1≤n,k≤107）。

输出要求

对于每一个测试用例，如果 n 能够表示为 k 个不同的正奇数之和，那么就打印 “YES”（不带引号），否则就打印 “NO”。

以下是一些输入输出的示例帮助理解：

输入示例：

输出示例：

YES
YES
NO
YES
YES
NO

具体说明示例情况如下：

在第一个测试用例中，3 可以直接表示为 3 本身（它就是奇数）。
在第二个测试用例中，4 可以表示为 1 + 3，是两个不同的正奇数之和。
在第三个测试用例中，10 无法表示成三个不同的正奇数之和。
在第四个测试用例中，10 可以表示为 3 + 7 这样两个不同正奇数的和。
在第五个测试用例中，16 能够表示为 1 + 3 + 5 + 7，即四个不同的正奇数之和。
在第六个测试用例中，16 不能表示为 5 个不同的正奇数之和。

二、Python 代码实现

以下是使用 Python 语言编写的用于解决该问题的代码：

def can_represent_sum(n, k):# 计算 k 个最小奇数的和min_sum = k * k# 如果 n 小于最小和，或者 n 和 k 的奇偶性不同，则返回 "NO"if n < min_sum or (n % 2!= k % 2):return "NO"else:return "YES"def main():# 读取测试用例数量t = int(input())results = []for _ in range(t):# 读取 n 和 kn, k = map(int, input().split())results.append(can_represent_sum(n, k))# 输出所有结果print("\n".join(results))if __name__ == "__main__":main()

代码详细说明

can_represent_sum 函数：
- 计算最小奇数和：通过数学规律可知，前 k 个最小奇数 1 + 3 + 5 +... + (2*k - 1) 的和可以用公式 k * k 来计算得出。例如，当 k = 3 时，对应的三个最小奇数为 1、3、5，它们的和就是 3 * 3 = 9。
- 判断条件：
  - 首先判断 n 是否大于等于这个最小奇数和，即 n >= k * k，只有满足这个条件，n 才有可能表示成 k 个不同正奇数的和，因为如果 n 比这个最小和还小，那肯定无法满足要求。
  - 同时还要判断 n 和 k 的奇偶性是否相同，因为奇数个奇数相加结果为奇数，偶数个奇数相加结果为偶数。如果 n 和 k 的奇偶性不一致，也无法满足 n 能表示为 k 个不同正奇数之和的要求。若上述两个条件都满足，则返回 “YES”，否则返回 “NO”。
main 函数：
- 先是读取输入的测试用例数量 t，接着初始化一个空列表 results，用于存放每个测试用例的判断结果。
- 通过循环逐个读取每一组 n 和 k 的值，并调用 can_represent_sum 函数来判断该组数据是否满足要求，将结果添加到 results 列表中。
- 最后通过 print("\n".join(results)) 将列表中的结果逐行输出。