首页 > 试题广场 >

小红的完全平方数

[编程题]小红的完全平方数
  • 热度指数：283 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
\,\,\,\,\,\,\,\,\,\,小红有一个长度为 n 的整数数组 \{a_1,a_2\dots,a_n\} ，如果从数组中任选两个数 a_i, a_j (i \neq j)，他们的乘积都是完全平方数，那么这个数组就是好数组。
\,\,\,\,\,\,\,\,\,\,如果现在的数组不是一个好数组，小红可以执行任意多次操作：
\,\,\,\,\,\,\,\,\,\,\,\,\,\,\bullet\,从数组里选择一个数，将其乘以一个正整数 x ；
\,\,\,\,\,\,\,\,\,\,她想知道，最少需要多少次操作才能使数组变成好数组。

\,\,\,\,\,\,\,\,\,\,如果一个数可以被表示为一个整数的平方，那么这个数就是完全平方数。

输入描述:
\,\,\,\,\,\,\,\,\,\,第一行输入一个整数 n\left(1 \leq n \leq 10^5\right) 代表数组中元素的数量。
\,\,\,\,\,\,\,\,\,\,第二行输入 n 个整数 a_1, a_2, \dots, a_n\left(1 \leq a_i \leq 10^6\right) 代表数组中的元素。


输出描述:
\,\,\,\,\,\,\,\,\,\,在一行上输出一个整数，代表最少需要的操作次数。
示例1

输入

4
1 1 4 2

输出

1

说明

\,\,\,\,\,\,\,\,\,\,将第四个数乘 2 即可，获得 [1, 1, 4, 4] ，其中任意两个数的和乘积为完全平方数。
示例2

输入

5
1 2 3 4 5

输出

3
算法知识视频讲解
开通博客
头像 丨阿伟丨
发表于 2025-09-12 17:55:06
题目链接 小红的完全平方数 题目描述 给定一个长度为 的整数数组。如果数组中任意两个数 的乘积都是完全平方数，则称该数组为“好数组”。 小红可以执行操作：选择数组中的一个数，将其乘以任意正整数。她想知道，最少需要多少次操作才能使数组变成一个“好数组”。 解题思路 这是一个最优化问题，关键在于将“ 展开全文
去ta的博客 赞 (2) 回复(0) 收起

问题信息

数组 哈希 数论 阿里云
难度：
2条回答 849浏览

热门推荐

相关试题

小红的完全平方数

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号