F - Minimum Sum of Array-蒲公英云

F - Minimum Sum of Array

傷城~ 2022-03-19 15:22 237阅读 0赞

You are given an array a consisting of n integers a1, …, a**n. In one operation, you can choose 2 elements a**i and a**j in which a**i is divisible by a**j and transform a**i to a**j.

A number x is said to be divisible by a number y if x can be divided by y and the result is an exact whole number. For example, 15 is divisible by 3, because 15÷ 3 = 5 exactly, but 9 is not divisible by 2 because 9÷ 2 is 4 with 1 left over.

Your task is to find the minimum sum of the array a that can be obtained by making as many transform operations as you want. Can you?

Input

The first line contains an integer T (1 ≤ T ≤ 100) specifying the number of test cases.

The first line of each test case contains an integer n (1 ≤ n ≤ 105), in which n is the size of array a. Then a line follows containing n integers a1, …, a**n (1 ≤ a**i ≤ 106), giving array a.

The sum of n overall test cases does not exceed 3 × 106.

Output

For each test case, print a single line containing the minimum sum of the array athat can be obtained after making as many transform operations as you want.

Example

Input

1
5
2 2 3 6 6

Output

废柴的一天。。。。

这题用了埃氏筛法，1e6*1e6的复杂度过了我也是醉了

思维：用一个数组V记录每个数字出现的次数模拟埃氏筛如果某个 I 被筛到 I*J那么吧 J 的数字全部变成I

WA因：因为long long 是lld输出（输出格式错误）

#include<bits/stdc++.h>
using namespace std;
int t,n,a[100005],v[1000005];
int main(){
    scanf("%d",&t);
    while(t--){
        long long sum=0;
        scanf("%d",&n);
        memset(v,0,sizeof(v));
        for(int i=1;i<=n;i++){
            scanf("%d",&a[i]);
            v[a[i]]++;
            sum+=a[i];
        }
        for(int i=1;i<=1000000;i++){
            if(v[i]){
                for(int j=2;i*j<=1000000;j++)
                    if(v[i*j]){
                        sum=sum-v[i*j]*i*j+i*v[i*j];                        
                        v[j*i]=0;
                    }
            }
        }
        printf("%lld\n",sum);//。。有点崩溃  这是输出格式错误的原因 
    }
    return 0;
}