解题思路

• 将下标按相同的值 ⌊n/i⌋ 分组。对每个分组内的任意两元素，我们可以把它们同时变成它们的 gcd，该操作可无限次执行。
• 关键性质：在同一分组内，经过若干次操作，可以把该分组的所有元素都变成该分组所有元素的整体最大公约数 G（因为两两替换为 gcd 可逐步把所有数“收缩”到整体 gcd）。这样该分组的元素和变为 组大小 × G，且这是最小值。
• 因而答案为：对所有分组求其元素 gcd 并乘以分组大小后累加。
• 实现要点：⌊n/i⌋ 的取值个数是 O(√n)。可用分块：令 l=1，令 q=n//l，则区间 [l, r]（其中 r=n//q）的下标满足同一 ⌊n/i⌋。遍历这些区间即可。

复杂度分析

题目内容

给定一个长度为$n$ 的数组{$a_1,a_2,...,a_n$} 。 你可以对数组执行以下操作任意次：

• 选择两个不同的下标$i,j$ ，满足$1≤i≤j$ 且[$n/i$]=[$n/j$] ；
• 将$a_i$ 与$a_j$ 同时替换为$gcd(a_i,a_j)$ 。 请输出操作后（或者不执行任何操作）数组所有元素之和的最小值。

【名词解释】

• $[x]$：代表对 $x$进行下取整操作，得到不超过 $x$的最大整数。
• 最大公约数（$gcd$）：指两个或多个整数共有约数中最大的一个。例如，$12$ 和 $30$ 的公约数有$1, 2, 3, 6$，其中最大的约数是$6$，因此记作$gcd(12,30)=6$ 。

输入描述

每个测试文件均包含多组测试数据。第一行输入一个整数$T(1≤T≤10^4)$代表数据组数，每组测试数据描述如下：

• 第一行输入一个整数$n(1≤n≤2×10^5)代$表数组长度；
• 第二行输入$n$个整数 $a_1,a_2,...,a_n(1≤a_i≤10^9)$代表数组中的元素； 除此之外，保证单个测试文件的$n$之和不超过$2×10^5$ 。

输出描述

对于每一组测试数据，新起一行输出一个整数，表示操作后数组所有元素之和的最小值。

样例1

输入

1 
6
1 2 3 7 8 9

输出

9