我们需要判断是否存在 $a \ge 1$ 、 $k \ge 3$ ，使得 $x=a(a+1)\cdots(a+k-1)$ 。
直接预处理：枚举所有起点 $a$ 和长度，生成不超过 $10^9$ 的所有连续正整数乘积放入集合，查询时 $O(1)$ 判断是否在集合中。
枚举上界：因为最短长度为 $3$ ，必有 $a(a+1)(a+2) \le 10^9$ 。可知 $a \lesssim 1000$ ；而从 $1$ 开始累乘，长度超过约 $13$ 时已超过 $10^9$ 。因此预处理规模很小。
正确性：若 $x$ 可表示为某段连续正整数乘积，则该段会在预处理枚举中出现。

P3481.第1题-完美数字

1000ms

Difficulty: 4

所属公司 : 小红书

算法与标签>暴力枚举

题目内容

用户的每一次点赞都代表着对内容的喜爱。小红定义一个正整数 $x$ 为完美数字 当且仅当同时满足以下两个条件：

现在小红薯接收到多次 $Plog$ 点赞数查询，每次给出一个正整数 $x$ ，请帮助小红薯判断该点赞数是否为完美数字。

每个测试文件均包含多组测试数据。第一行输入一个整数 $T(1≤T≤10^4)$ 代表数据组数，每组测试数据描述如在一行上输入一个整数 $x(1≤x≤10^9)$ ，表示一次点赞数查询。

对于每组测试数据，新起一行，如果点赞数是完美数字，输出 $YES$ ；否则，输出 $NO$ 。

输入

输出

YES
NO
YES

输入

预期输出（选填）