HDU-5902-GCD is Funny解题笔记

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

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

It can be seen that after performing the move n−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 T (1≤T≤100), indicating the number of test cases. For each test case:

The first line contains an integer n (3≤n≤500) -- the number of integers written on the board. The next line contains n integers: a1,a2,...,an (1≤ai≤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

题意：Alex发明了一个有趣的游戏. 一开始他在黑板上写了n个正整数, 然后他开始重复进行如下的操作:     1. 他选择黑板上三个数字a, b和c, 把他们从黑板上擦掉.
    2. 他从这三个数a, b和c中选择了两个数, 并计算出他们的最大公约数, 记这个数为d (d 可以是gcd(a,b), gcd(a,c)或者gcd(b,c)).
    3. 他在黑板上写下两次数字d. 显然, 在操作n−2次后, 黑板上只会留下两个相同的数字. Alex想要知道哪些数字可以最终留在黑板上.
解题思路：原数列中的数两两GCD的结果必可保留，产生的新数与原数列还能继续两两GCD产生新数，如此再进行n-3次操作，若没有新数生成则跳出。

#include <algorithm>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <iostream>
#include <cstdlib>
#include <set>
#include <vector>
#include <cctype>
#include <iomanip>
#include <sstream>
#include <climits>
#include <queue>
#include <stack>
using namespace std;
typedef long long ll;
#define INF 0X3f3f3f3f
const ll MAXN = 1e3 + 7;
const ll MOD = 1e9 + 7;
int GCD(int a, int b)
{
    return b == 0 ? a : GCD(b, a % b);
}
int num[MAXN];
int ans[MAXN];
int main()
{
    ios::sync_with_stdio(0);
    int t;
    cin >> t;
    while (t--)
    {
        memset(ans, 0, sizeof(ans));
        int n;
        cin >> n;
        for (int i = 0; i < n; i++)
            cin >> num[i];
        for (int i = 0; i < n - 1; i++)
            for (int j = i + 1; j < n; j++)
                ans[GCD(num[i], num[j])] = 1;
        int cnt = n;
        bool run = true;
        while (cnt-- >= 4 && run)
        {
            run = false;
            for (int i = 1; i <= 1000; i++)
                if (ans[i])
                    for (int j = 0; j < n; j++)
                    {
                        if (!ans[GCD(num[j], i)])
                        {
                            ans[GCD(num[j], i)] = 1;
                            run = true;
                        }
                    }
        }
        bool flag = false;
        for (int i = 1; i <= 1000; i++)
        {
            if (ans[i])
            {
                if (!flag)
                {
                    flag = true;
                    cout << i;
                }
                else
                    cout << ' ' << i;
            }
        }
        cout << endl;
    }
    return 0;
}