解题思路
1. 初始最大公因数
先计算整个数组的最大公因数为
g=gcd(a1,a2,…,an)g = \gcd(a_1, a_2, \ldots, a_n) g=gcd(a1 ,a2 ,…,an )
2. 操作效果分析
操作步骤:
* 选定一个子序列,其最大公因数为 gsg_sgs 。
* 对子序列中每个元素 abia_{b_i}abi 变为
abi′=abi×(gs+1)gsa'_{b_i} = \frac{a_{b_i} \times (g_s + 1)}{g_s} abi ′ =gs abi ×(gs +1)
因为 gs∣abig_s \mid a_{b_i}gs ∣abi ,分数是整数。
3. 操作后数组最大公因数的变化
设操作后整体数组最大公因数为 G′G'G′,子序列中元素的变化相当于将它们乘以 gs+1gs\frac{g_s + 1}{g_s}gs gs +1 。
目标是选取子序列使得 G′G'G′ 最大。
4. 关键观察
* 操作只进行一次。
* 选择子序列对应的最大公因数 gsg_sgs 必须满足:
gsg_sgs 是数组中某些元素的最大公因数。
* 操作后,子序列元素的公因数变为 gs+1g_s+1gs +1。
* 其他未选元素保持不变,最大公因数变为这些元素与操作后子序列元素公因数的 gcd\gcdgcd。
5. 转化
* 假设未选元素的最大公因数为 grestg_{rest}grest 。
* 操作后整体最大公因数为
G′=gcd(gs+1,grest)G' = \gcd(g_s + 1, g_{rest}) G′=gcd(gs +1,grest )
* 为了最大化 G′G'G′,枚举所有可能的 gsg_sgs :
* gsg_sgs 是数组中存在的某个因子。
* 统计数组中所有是 gsg_sgs 倍数的元素(即可构成子序列)。
* 计算剩下元素的最大公因数 grestg_{rest}grest 。
* 计算 gcd(gs+1,grest)\gcd(g_s + 1, g_{rest})gcd(gs +1,grest ),更新答案。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
代码解释