本文共 1119 字，大约阅读时间需要 3 分钟。

为了解决这个问题，我们需要计算一个集合是否是JZP集。JZP集的定义是，对于任意集合中的两个数x和y，如果(x+y)/2是整数，那么这个中间值也必须在集合中。通过分析，我们发现满足条件的集合中的元素必须形成等差数列，且公差必须是奇数。

方法思路

为了高效计算，特别是当n很大时，我们采用了动态规划和预处理的方法。具体步骤如下：

解决代码

import sys
def main():
    max_n = 10**7
    # 预处理每个数被奇数整除的次数
    cnt = [0] * (max_n + 1)
    for d in range(1, max_n + 1):
        if d % 2 == 1:  # d是奇数
            for multiple in range(d, max_n + 1, d):
                cnt[multiple] += 1
    # 计算dp数组
    dp = [0] * (max_n + 1)
    dp[1] = 2  # 当n=1时，有空集和{1}
    for n in range(2, max_n + 1):
        temp = cnt[n-1]
        dp[n] = dp[n-1] + 1 + temp  # 加上空集、{n}和各d的贡献
    # 处理输入输出
    input = sys.stdin.read().split()
    T = int(input[0])
    for i in range(1, T + 1):
        n = int(input[i])
        print(f"Case #{i}: {dp[n]}")
if __name__ == "__main__":
    main()

代码解释

这种方法通过预处理和动态规划，有效地将时间复杂度降低到O(n log n)，能够高效处理大规模输入。

转载地址：http://dwhfk.baihongyu.com/