#P1699. 2024.03.16-MY-第三题-数组变换
2024.03.16-MY-第三题-数组变换
![](https://s3.bmp.ovh/imgs/2024/09/03/9ec1757951030a02.jpg)
塔子哥有一个长度为 n 的数组 a。他想要使得所有ai的最大公因子是一个素数。即:gcd(a1,a2,...,an)是一个素数。他可以对数组进行任意次操作。具体的:每次操作,他会选择i,j两个下标,同时执行:ai=ai+2,aj=aj−2
请问他是否有可能在任意次操作内将数组变成符合要求的,如果可以,请输出所有可能的最大公因数。注意,这里要保证aj,在操作后仍然是正数,即不能选择aj≤2.
输入两行,第一行一个正整数n(2≤n≤2∗1e5)表示数组长度。
第二行n个整数ai([1,1e6])。
输入包含一行或两行。如果可以输出“YES”否则输出“NO”(不含双引号)
如果答案为“YES”,则第二行按照升序输出所有可行的数组 gcd.
输入
4
1 3 5 9
输出
YES
3
说明
可以选择一次i=1,j=3,这样一来数组变成:[3,3,3,9], gcd =3.可以证明只有 3这一个答案。
输入
4
2 2 2 2
输出
YES
2
扫码备注加群即可,期待您的到来~
By signing up a CodeFun2000 universal account, you can submit code and join discussions in all online judging services provided by us.