[蓝桥杯青少年组国赛 2025] 第三题

Luogu

IDLGB4398

Time1000ms

Memory512MB

DifficultyP3

2025数论素数判断,质数,筛法蓝桥杯青少年组

给定一个包含 $n$ 个正整数的序列 $A = [a_1, a_2, \dots, a_n]$。你需要从中找出一个**子序列**，使得该子序列中任意两个不同元素的乘积都是一个**完全平方数**。你的任务是求出满足条件的**最长**子序列的长度。 **提示：** * **子序列**：从原序列中删除零个或多个元素，其余元素保持原有顺序得到的序列。例如，$[2, 3, 18]$ 是 $[2, 8, 3, 18, 12]$ 的一个子序列。 * **完全平方数**：一个整数，它可以表示为另一个整数的平方。例如，36 是一个完全平方数，因为 $36 = 6^2$。 ## Input 输入共两行。第一行包含一个整数 $n$，表示序列的长度。第二行包含 $n$ 个用空格隔开的正整数 $a_1, a_2, \dots, a_n$，表示序列中的元素。 ## Output 输出一个整数，表示满足条件的最长子序列的长度。 [samples] ## Background 洛谷的试题为民间回忆版，仅保证题意相同。试题呈现形式、样例、数据范围可能存在差异。 ## Note ### 样例解释我们可以找到一个满足条件的子序列 $[2, 8, 18]$，其长度为 3。 ### 数据范围与约定对于 100% 的数据，满足 $1 \le n \le 10^5$，$1 \le a_i \le 10^{7}$。

Samples

Input #1

5
2 8 3 18 12

Output #1

API Response (JSON)

{
  "problem": {
    "name": "[蓝桥杯青少年组国赛 2025] 第三题",
    "description": {
      "content": "给定一个包含 $n$ 个正整数的序列 $A = [a_1, a_2, \\dots, a_n]$。 你需要从中找出一个**子序列**，使得该子序列中任意两个不同元素的乘积都是一个**完全平方数**。 你的任务是求出满足条件的**最长**子序列的长度。 **提示：** *   **子序列**：从原序列中删除零个或多个元素，其余元素保持原有顺序得到的序列。例如，$[2, 3, 18]$ 是 $[2",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 524288
    },
    "difficulty": {
      "LuoguStyle": "P3"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGB4398"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "给定一个包含 $n$ 个正整数的序列 $A = [a_1, a_2, \\dots, a_n]$。\n\n你需要从中找出一个**子序列**，使得该子序列中任意两个不同元素的乘积都是一个**完全平方数**。\n\n你的任务是求出满足条件的**最长**子序列的长度。\n\n**提示：**\n*   **子序列**：从原序列中删除零个或多个元素，其余元素保持原有顺序得到的序列。例如，$[2, 3, 18]$ 是 $[2...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments