本文详细介绍了2018年CCPC桂林站G题——最大公约数（Greatest Common Divisor）的解题思路。通过分析原数组与差分数组的性质，提出通过寻找差分数组的公约数及其因数来确定最小操作次数。文章涵盖了预处理、差分数组计算、因数分解和特殊情况处理等关键步骤，并提供了完整的C++代码实现。
GCD题解
题源：2018CCPC桂林站：G. Greatest Common Divisor
题目描述
题意理解
输入 T T T 组数据，每组数据含有两 n n n 个整数，进行 n n n 个数整体 + 1 +1 +1 的操作，求最少进行几次， n n n 个数有公约数，如果无解，输出 − 1 -1 −1，不需要进行操作就满足条件时，输出 0。
数据范围为： T [ 1 , 20 ] T \ [1,20] T [1,20] ， n [ 1 , 1 0 5 ] n \ [1,10^{5}] n [1,105] , x [ 1 , 1 0 9 ] x \ [1,10^{9}] x [1,109]
输出格式为： C a s e 1 : − 1 Case \quad 1: \quad -1 Case1:−1
原理分析
直观分析可知，在每次 + 1 +1 +1 操作时，数组不变的性质是其对应的差分数组即临项之差，所以从差分数组入手，研究其性质。
分析题例的差分数组：
-
原数组： 3 , 5 , 7 , 9 , 11 3,5,7,9,11 3,5,7,9,11
-
差分数组： 2 , 2 , 2 , 2 2,2,2,2 2,2,2,2
-
组合数组： 3 , 2 , 2 , 2 , 2 3,2,2,2,2 3,2,2,2,2
-
操作数组： 4 , 2 , 2 , 2 , 2 4,2,2,2,2 4,2,2,2,2
-
最大公约数： 2 2 2
分析可知，原数组公约数决定于差分数组的公约数，因为公约数意味着数组的每个数与这个数均有倍数关系，假设其中两项 a , b a,b a,b 的公约数位 t t t 那么 b − a = k t b-a=kt b−a=kt ，即二者差值一定是 t t t 的整数倍，推广至数组中所有数，则有：
-
原数组： x 1 , x 2 , x 3 , x 4 , x 5 x_1,x_2,x_3,x_4,x_5 x1,x2,x3,x4,x5
-
差分数组： x 2 − x 1 , x 3 − x 2 , x 4 − x 3 , x 5 − x 4 x_2-x_1,x_3-x_2,x_4-x_3,x_5-x_4 x2−x1,x3−x2,x4−x3,x5−x4 ，即 a 1 t , b 1 t , c 1 t , d 1 t a_1t,b_1t,c_1t,d_1t a1t,b1t,c1t,d1t
-
其中 t = g c d ( x 2 − x 1 , x 3 − x 2 , x 4 − x 3 , x 5 − x 4 ) t=gcd(x_2-x_1,x_3-x_2,x_4-x_3,x_5-x_4)
最低0.47元/天 解锁文章
扫一扫
357
被折叠的 条评论
为什么被折叠?
到【灌水乐园】发言
