F - Minimum Sum of Array

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

You are given an array *a* consisting of *n* integers *a*1, ..., *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 *a*1, ..., *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 *a*that 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;
    }