首页 > 试题广场 >

xgcd

[编程题]xgcd
  • 热度指数：557 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
小红有一个长度为 n 的数组 a。

她每次可以选定任意的 i,j(1\leq i,j\leq n)，然后将 a_i\rightarrow a_i\times a_j，a_j\rightarrow \text{lcm}(a_i,a_j)，两个操作是同时进行的，没有先后顺序。

小红想知道，把整个数组变成全部都是偶数元素的最少操作次数，若始终无法全变成偶数，输出 -1。

输入描述:
第一行输入一个正整数 n(1\leq n\leq 10^5)，表示数组 a 的长度。

第二行输入 n 个正整数，表示数组 a，其中 1\leq a_i\leq 10^9。


输出描述:
输出一个整数，表示把整个数组变成全部都是偶数元素的最少操作次数，若始终无法全变成偶数，输出 -1。
示例1

输入

2
1 2

输出

1
示例2

输入

2
1 1

输出

-1
算法知识视频讲解
开通博客
头像 丨阿伟丨
发表于 2025-09-12 14:41:03
题目链接 小红的数组变换 (注：链接题目操作为 a[j] -> a[i] * a[j]，但奇偶性逻辑与本题 lcm 操作完全相同) 题目描述 小红有一个长度为 的数组 。 她每次可以选定任意的 ，然后同时执行以下两个操作： 小红想知道，把整个数组变成全部都是偶数元素的最少操作次数是多 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 weison周
发表于 2025-06-27 10:30:56
""" 算法解释 1、统计奇偶个数：遍历数组，统计奇数和偶数的数量 2、特殊情况处理： 无偶数时返回 - 1 全为偶数时返回 0 3、计算操作次数： 当有至少 2 个偶数时，每个奇数只需 1 次操作变为偶数 当只有 1 个偶数时，需要 1 次额外操作生成第二个偶数，再处 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 牛小白2025
发表于 2025-08-19 09:39:29
""" 算法解释 1、统计奇偶个数：遍历数组，统计奇数和偶数的数量 2、特殊情况处理： 无偶数时返回 - 1 全为偶数时返回 0 3、计算操作次数： 若至少有一个偶数，则只需统计奇数个数=操作次数 """ def min_operation 展开全文
去ta的博客 赞 (0) 回复(0) 收起

问题信息

贪心 基础数学 阿里云
难度：
0条回答 226浏览

热门推荐

相关试题

xgcd

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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