{"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, 8, 3, 18, 12]$ 的一个子序列。\n*   **完全平方数**：一个整数，它可以表示为另一个整数的平方。例如，36 是一个完全平方数，因为 $36 = 6^2$。\n\n## Input\n\n输入共两行。\n\n第一行包含一个整数 $n$，表示序列的长度。\n\n第二行包含 $n$ 个用空格隔开的正整数 $a_1, a_2, \\dots, a_n$，表示序列中的元素。\n\n## Output\n\n输出一个整数，表示满足条件的最长子序列的长度。\n\n[samples]\n\n## Background\n\n洛谷的试题为民间回忆版，仅保证题意相同。试题呈现形式、样例、数据范围可能存在差异。\n\n## Note\n\n### 样例解释\n\n我们可以找到一个满足条件的子序列 $[2, 8, 18]$，其长度为 3。\n\n### 数据范围与约定\n\n对于 100% 的数据，满足 $1 \\le n \\le 10^5$，$1 \\le a_i \\le 10^{7}$。","is_translate":false,"language":"English"}],"meta":{"iden":"LGB4398","tags":["2025","数论","素数判断,质数,筛法","蓝桥杯青少年组"],"sample_group":[["5\n2 8 3 18 12","3"]],"created_at":"2026-03-03 11:09:25"}}