BestCoder Round #87 1001

GCD is Funny

Accepts: 524

Submissions: 1147

Time Limit: 4000/2000 MS (Java/Others)

Memory Limit: 65536/65536 K (Java/Others)

Problem Description

Alex has invented a new game for fun. There are nnn integers at a board and he performs the following moves repeatedly:

1. He chooses three numbers aaa, bbb and ccc written at the board and erases them.
2. He chooses two numbers from the triple aaa, bbb and ccc and calculates their greatest common divisor, getting the number ddd (ddd maybe gcd(a,b)gcd(a,b)gcd(a,b), gcd(a,c)gcd(a,c)gcd(a,c) or gcd(b,c)gcd(b, c)gcd(b,c)).
3. He writes the number ddd to the board two times.

It can be seen that after performing the move n−2n-2n−2 times, there will be only two numbers with the same value left on the board. Alex wants to know which numbers can left on the board possibly. Can you help him?

Input

There are multiple test cases. The first line of input contains an integer TTT (1≤T≤100)(1 le T le 100)(1≤T≤100), indicating the number of test cases. For each test case:

The first line contains an integer nnn (3≤n≤500)(3 le n le 500)(3≤n≤500) -- the number of integers written on the board. The next line contains nnn integers: a1,a2,...,ana_1, a_2, ..., a_na​1​​,a​2​​,...,a​n​​ (1≤ai≤1000)(1 le a_i le 1000)(1≤a​i​​≤1000) -- the numbers on the board.

Output

For each test case, output the numbers which can left on the board in increasing order.

Sample Input

3
4
1 2 3 4
4
2 2 2 2
5
5 6 2 3 4

Sample Output

1 2
2
1 2 3
题意很简单 就是找n中任意两个数的最大最大公约数，我最开始选择用数组去存，结果超时了 ，导致wa了三遍，
后来选择用map去存

#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<map>
#include<algorithm>
typedef long long ll;
using namespace std;
int test[1006];
int test2[1006];
int GCD(int a,int b)
{
    if(a < b)
        int temp = a, a = b, b = temp;
    if(b == 0)  return a;
    return GCD(b,a%b);
}
int main()
{
    int t;
    int i,j;
    int n;
    scanf("%d",&t);
    map<int,int>test2;
    while(t--)
    {
        scanf("%d",&n);
        for(i=1;i<=n;i++)
            scanf("%d",&test[i]);
        int tt;
        for(i=1;i<n;i++)
        {
            for(j=i+1;j<=n;j++)
            {
                tt=GCD(test[i],test[j]);
                test2[tt]=1;
            }
        }
        map<int,int>::iterator it;
        int flag=1;
        for(it=test2.begin();it!=test2.end();it++)
        {
            if(flag==1)
                printf("%d",it->first);
            else
                printf(" %d",it->first);
            flag=0;
        }
        test2.clear();
        printf("
");
    }

}