首页 > 试题广场 >

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
算法知识视频讲解
添加回答

这道题你会答吗？花几分钟告诉大家答案吧！

提交观点

问题信息

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

热门推荐

相关试题

xgcd

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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