题解
题面描述
给定一个长度为 n 的数组 {a1,a2,…,an}，定义数组的权值为数组所有元素之和。你可以执行任意次以下操作，以使数组权值最小化：
- 选择两个索引 i 和 j；
- 任意选取两个正整数 x 和 y，但需满足gcd(x,y)=gcd(ai,aj);
P3274.第2题-最小化数组权值
题目内容
给定一个长度为n的数组{a1,a2,…,an}，定义数组的权值为数组所有元素之和。你可以执行任意次以下操作，以使数组权值最小化：
- 选择两个索引 i 和 j ；
- 任意选取两个正整数 x 和 y ，但需满足 gcd(x,y)=gcd(ai,aj)；
- 将 ai←x，ai←y 。
输入描述
每个测试文件均包含多组测试数据。 第一行输入一个整数 T(1≤T≤104)，表示测试组数；随后对于每组数据，依次输入： 第一行输入一个整数 n(1≤n≤2×105) ，表示数组长度； 第二行输入 n 个整数 a1,a2,…,an(1≤ai≤109) ，表示数组元素。此外，保证所有测试数据中 ∑n≤2×105 。
输出描述
对于每个测试用例，在一行上输出一个整数，表示经过任意次操作后能够得到的最小数组权值。
样例1
输入
2
2
1 2
3
3 7 9
输出
2
3
说明
在第二个测试用例中，可以先选择 (i,j)=(1,2) ，gcd(3,7)=1 。取 x=y=1 得到{1,1,9}； 再选择 (i,j)=(2,3) ，gcd(1,9)=1，取 x=y=1 得到{1,1,1}，权值为 3 。
