P4268.第2题-数组操作
题目内容
给定一个长度为n 的数组{a1,a2,...,an} 。 你可以对数组执行以下操作任意次：
- 选择两个不同的下标i,j ，满足1≤i≤j 且[n/i]=[n/j] ；
- 将ai 与aj 同时替换为gcd(ai,aj) 。 请输出操作后（或者不执行任何操作）数组所有元素之和的最小值。
【名词解释】
- [x]：代表对 x进行下取整操作，得到不超过 x的最大整数。
- 最大公约数（gcd）：指两个或多个整数共有约数中最大的一个。例如，12 和 30 的公约数有1,2,3,6，其中最大的约数是6，因此记作gcd(12,30)=6 。
输入描述
每个测试文件均包含多组测试数据。第一行输入一个整数T(1≤T≤104)代表数据组数，每组测试数据描述如下：
- 第一行输入一个整数n(1≤n≤2×105)代表数组长度；
- 第二行输入n个整数 a1,a2,...,an(1≤ai≤109)代表数组中的元素； 除此之外，保证单个测试文件的n之和不超过2×105 。
输出描述
对于每一组测试数据，新起一行输出一个整数，表示操作后数组所有元素之和的最小值。
样例1
输入
1
6
1 2 3 7 8 9
输出
9
