Mike and gcd problem | Serendipity

type

status

date

slug

summary

题目描述

迈克有一个长度为的序列。如果序列中所有元素的gcd都大于 1 ，他就认为这个序列很美，即。

Mike 想改变他的序列，使其更加美观。他可以选择一个索引，删除数字，并按照这个顺序将数字放到它们的位置上。他希望进行尽可能少的运算。如果可能，请找出使数列变美的最少运算次数，或者告诉他不可能这样做。是最大的非负数，使得除于为。

第一行包含一个整数 - 序列的长度。

第二行包含个空格分隔的整数 - 序列 A 的元素。

如果可以通过执行上述操作使序列变美，则在第一行输出"YES"(不带引号)，否则输出"NO"(不带引号)。

如果答案是"YES"，则输出使序列优美所需的最小步数

在第一个示例中，你只需移动一次，就可以得到序列 [0, 2] ，其中有。

在第二个示例中，序列中的已经大于。

这是一道思维题，不管数据怎么样，输出结果都是“YES”。如果，直接输出0，否则。

先来解释一下为什么输出肯定是“YES”：

对于两相邻的数，如果要进行操作，操作一次后变为 a-b，a+b，在操作一次变成 -2b，2a，也就是说，只要操作足够多的次数，最后这个数列一定可以到达2，也就是输出“YES“。

下面来证明为什么要操作的话最终的一定是2：

证明：设x=gcd(a_i, a_{i+1})，ai = ax, a_{i+1} = bx

操作后a_i=(a-b)x, a_{i+1} =(a+b)x

则 gcd(a_i, a_{i+1})= gcd((a-b)x, (a+b)x)=x*gcd(a -b, a+b)

设gcd(a-b, a+b)=k, a-b=a’k, a+b=b’k

那么(a-b)+(a+b)=a'k+b’k, (a+b)-(a-b)=b’k-a’k

所以 2a =a'k+b'k, 2b=b’k-a’k

因为 gcd(2a, 2b)=2×gcd(a, b)=2

所以gcd(a'k + b’k, b’k-a’k)=k* gcd(a’ +b’, b’ -a’)=2

可得k=1或k=2

故gcd(a_i, a_{i+1})=x*k=x或2x

下面给出完整代码：

（这次代码写的比较垃圾，建议根据前面的思维证明自己写。）