首页 > 试题广场 >

小苯的GCD

[编程题]小苯的GCD
  • 热度指数：59 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
小苯有一个长度为 n 的数组 a。
他想要使得所有 a_i 的最大公因子是一个素数。即：gcd(a_1, a_2, ... , a_n) 是一个素数。他可以对数组进行任意次操作。
具体的：每次操作，他会选择 i, j 两个下标，同时执行：
  a_i=a_i + 2, a_j = a_j - 2。

请问他是否有可能在任意次操作内将数组变成符合要求的，如果可以，请输出所有可能的最大公因数。
注意，这里要保证 a_j 在操作后仍然是正数，即不能选择 a_j \leq 2。

输入描述:
输入包含两行。
第一行一个正整数 n (2 \leq n \leq 2 \times 10^5) 表示数组长度。
第二行 n 个正整数a_i (1 \leq a_i \leq 10^6) 表示这个数组。


输出描述:
输入包含一行或两行。
如果可以输出“YES”，否则输出“NO”（不含双引号）。
如果答案为“YES”，则第二行按照升序输出所有可行的数组 gcd。
示例1

输入

4
1 3 5 9

输出

YES
3

说明

可以选择一次 i = 1, j = 3，这样一来数组变成：[3, 3, 3, 9] ，gcd = 3。
可以证明只有 3 这一个答案。
示例2

输入

4
2 2 2 2

输出

YES
2
示例3

输入

5
2 4 5 6 8

输出

NO
示例4

输入

8
1324 4544 910 3087 14450 1010 2346 5836

输出

YES
3 17 73
算法知识视频讲解
添加回答

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

提交观点

问题信息

构造 数论
难度：
0条回答 187浏览

热门推荐

相关试题

小苯的GCD

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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