QOJ.ac

QOJ

Límite de tiempo: 1 s Límite de memoria: 256 MB Puntuación total: 100

#3571. 追求方正

Estadísticas

数字 6, 10, 15 本身都不是平方数,但它们的乘积 900 是一个平方数。 我们对乘积为平方数的正整数集合感兴趣。我们将这样的集合称为 HIP(意为“具有有趣的乘积”,Has Interesting Product)。显然,{6, 10, 15} 是一个 HIP 集合,{25} 也是。 更一般地,给定一个正整数集合,它是否包含非空的 HIP 子集?如果有,对于哪些 HIP 子集,其乘积是最小的? 为了简化问题,我们将研究范围限制在区间内。

输入格式

每个测试用例包含一行两个整数 $a$ 和 $b$ ($1 < a < b \le 4900$)。这些整数描述了区间 $A = \{ x \in \mathbb{N} \mid a \le x \le b \}$。

输出格式

对于每个测试用例,输出最小的数 $k$,使得 $A$ 的某个非空子集 $X \subseteq A$ 中元素的乘积等于 $k^2$。如果不存在这样的数,输出 ‘none’。数 $k$ 将小于 $2^{63}$。

样例

输入 1

20 30

输出 1

5

输入 2

101 110

输出 2

none

输入 3

2337 2392

输出 3

3580746020392020480

Discussions

About Discussions

The discussion section is only for posting: General Discussions (problem-solving strategies, alternative approaches), and Off-topic conversations.

This is NOT for reporting issues! If you want to report bugs or errors, please use the Issues section below.

Open Discussions 0
No discussions in this category.

Issues

About Issues

If you find any issues with the problem (statement, scoring, time/memory limits, test cases, etc.), you may submit an issue here. A problem moderator will review your issue.

Guidelines:

  1. This is not a place to publish discussions, editorials, or requests to debug your code. Issues are only visible to you and problem moderators.
  2. Do not submit duplicated issues.
  3. Issues must be filed in English or Chinese only.
Active Issues 0
No issues in this category.
Closed/Resolved Issues 0
No issues in this category.