JS's Blog
0%

Posted on Edited on In ,

题目链接：
http://acm.hdu.edu.cn/showproblem.php?pid=2841

题目大意：
在平面(1,1)(1,1)到(n,m)(n,m)两点之间的矩形中一共有n×mn\times m棵树，求站在点(0,0)(0,0)的人一共能看到多少棵没有被挡住的树？

分析：
如果一棵树的坐标为(x,y)(x,y)，且g=gcd(x,y)≠1g = gcd(x,y)\not=1 ，则(x′,y′)=(xg,yg)(x',y') = (\frac{x}{g},\frac{y}{g})，说明(x,y)(x,y)在点(0,0)(0,0)到点(x′,y′)(x',y')的线段延长线上，所以(x,y)(x,y)会被挡住

那么只要枚举所有满足坐标(x,y)(x,y)，gcd(x,y)=1gcd(x,y)=1的点即可，基本的容斥过程

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;
typedef long long ll;

const ll mod = 1e9+7;


const int maxn = 100000+10;
vector<int> ft[120005];
bool isprime[120000];

void init()
{
    for (int i = 2 ; i <= maxn ; i ++)
    {
        if (!isprime[i])
        {
            for (int j = i ; j <= maxn ; j += i)
            {
                isprime[j] = true;
                ft[j].push_back(i);
            }
        }
    }

}

ll solve(int x,int sta,ll n)
{
    int pos = 0;
    ll temp = 1;
    while (sta)
    {
        if (sta&1)
            temp *= ft[x][pos];
        pos ++;
        sta >>= 1;
    }

    return n/temp;
}

int m,n;

int main(){
    init();
    int T,t=1;
    scanf("%d",&T);
    while (T--)
    {
        scanf("%d%d",&m,&n);

        if (m>n)
            swap(m,n);
        ll ans = 0;
        for (int i = 1 ; i <= n ; i ++)
        {
            ans += m;
            for (int j = 1 ; j < (1<<ft[i].size()); j ++)
            {
                ll temp = solve(i,j,m);int cp = j,cnt = 0;
                //printf("cp = %n\t",cp);
                while (cp)
                {
                    cp -= cp&(-cp);
                    cnt++;
                }
                //printf("cnt = %n\n",cnt);
                if (cnt&1)  ans -= temp;
                else    ans += temp;
            }
            //printf("%d\n",ans);
        }
        printf("%lld\n",ans);



    }



    return 0;
}

Posted on Edited on In ,

题目链接：
http://acm.hdu.edu.cn/showproblem.php?pid=5778
题目大意：
给定一个数x，求正整数y≥2y\geq2，使得满足以下条件：
1.y−xy-x的绝对值最小
2.y的质因数分解式中每个质因数均恰好出现2次。

简单分析：
y的质因数分解式中每个质因数均恰好出现2次，显然y是个完全平方数，但不是所有的完全平方数满足每个质因数恰好出现2次，y−xy-x绝对值最小的数，显然当y\sqrt{y}在x\sqrt{x}附近且满足条件时，绝对值最小，对x\sqrt{x}分解质因数，若有一个因数出现2次以上，则不满足条件，减小此值，继续向下搜索，由于这样的数出现的非常频繁，所以复杂度不会爆，然后再从x+1\sqrt{x}+1开始向上查找，直到找到一个满足的值，比较两次找到的数的平方与x的绝对值，最后输出小的那个
注1：第二次从x+1\sqrt{x}+1开始主要是为了防止某个数x，x\sqrt{x}满足条件，但x+1\sqrt{x}+1也满足，且答案更小，
注2：由于y≥2y\geq2，还需要加特判当x≤4x\leq4时，y都只能等于4，4为最小的满足条件的y值，此时当输出4−x4-x

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
#include<stdio.h>
#include<algorithm>
#include<iostream>
#include<string.h>
#include<math.h>
using namespace std;

long long int x,y,temp;

bool cha(long long kai)
{
    long long int i;
    for(i=2;i*i<kai;i++)
    {
        if (kai%i==0)
	{
	    kai/=i;
	    if (kai%i==0)
	        return true;
	}
    }
    return false;
}
int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%lld",&x);
        long long kai1=(long long)sqrt(x);
        long long  kai2=kai1;
        while(cha(kai1))
        {
            kai1=kai1-1;
        }
        y=abs(kai1*kai1-x);
        kai2++;
        while(cha(kai2))
        {
            kai2=kai2+1;
        }
        y=min(y,abs(kai2*kai2-x));
        if (x<=4)
            y = 4-x;
        printf("%lld\n",abs(y));
    }
    return 0;
}

Posted on Edited on In ,

题目链接：
BC #80 B Segment
题意：
Rivendell非常神,喜欢研究奇怪的问题.
今天他发现了一个有趣的问题.找到一条线段x+y=qx+y=q,
令它和坐标轴在第一象限围成了一个三角形,然后画线连接了坐标原点和线段上坐标为整数的格点.
请你找一找有多少点在三角形的内部且不是线段上的点,并将这个数对P取模后告诉他.
输入p和q。q是质数且q≤1018q≤1018,1≤P≤10181≤P≤1018
​​分析：
答案的公式是ans=(q−2)∗(q−1)/2ans=(q−2)∗(q−1)/2;
但是因为p和q的范围太大！直接乘的话会爆long long！！！
所以需要手动写快速乘法，类似于快速幂的写法！！！

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <climits>
#include <cmath>
using namespace std;

int T;
long long q,p;

long long mul(long long a,long long b)
{
    long long res=0,tmp=a;
    while(b){
        if(b&1) res=(res+tmp)%p;
        tmp=(tmp+tmp)%p;
        b>>=1;
    }
    return res;
}

int main()
{
    freopen("80Bin.txt","r",stdin);
    scanf("%d",&T);
    while(T--){
        cin>>q>>p;
        if(q==2){
            printf("0\n");
            continue;
        }
        long long t=(q-1)/2%p;
        long long ans=mul(q-2,t);
        cout<<ans<<endl;
    }
    return 0;
}

Posted on Edited on In ,

题目链接：
http://acm.hdu.edu.cn/showproblem.php?pid=1251

题目大意：
Ignatius最近遇到一个难题,老师交给他很多单词(只有小写字母组成,不会有重复的单词出现),现在老师要他统计出以某个字符串为前缀的单词数量(单词本身也是自己的前缀).

分析：
读入单词直接插入即可，由于这里要查询的是以该前缀为起始的单词数量，所以在加单词的时候，不仅要在单词末尾加值，同时在路径上所有结点都应该价值，最后查询该单词的权值即可

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cmath>
using namespace std;

typedef long long ll;


struct Trie{
    Trie *next[26];
    int val;
    Trie(){
        val = 0;
        for (int i = 0 ; i < 26 ; i ++)
            next[i] = NULL;
    }
};

void addword(char *str,Trie* node)
{
    if (node->next[str[0]-'a']==NULL)
    {
        node->next[str[0]-'a'] = new Trie;
        node = node->next[str[0]-'a'];
        node->val ++;
    }
    else
    {
        node = node->next[str[0]-'a'];
        node->val ++;
    }
    //printf("%c\t",*str);
    str++;
    if (*str)
        addword(str,node);
    else
        return;
}

int query(char *str ,Trie *node)
{
    //printf("%c\t",*str);
    if (node->next[*str-'a']==NULL)
        return 0;
    else
        node= node->next[*str-'a'];
    ++str;
    if (*str)
        return query(str,node);
    else
        return node->val;
}

char str[100];


int main()
{
    Trie *head = new Trie;
    char ch;
    int cnt ;
    while (ch=getchar())
    {
        cnt = 0;
        if (ch=='\n')
            break;

        while (ch!='\n')
        {
            str[cnt++] = ch;
            ch = getchar();
        }
        str[cnt]=0;
        addword(str,head);
    }

    while (~scanf("%s",str))
    {
        int ans = query(str,head);
        printf("%d\n",ans);
    }
    return 0;
}

Posted on Edited on In ,

题目链接：
http://acm.hust.edu.cn/vjudge/contest/70017#problem/I
题目大意：
求调和级数前n项的和，T个样例，(1≤T≤10000，1≤n≤1081{\leq}T{\leq}10000 ，1 ≤ n ≤ 10^8)
分析：
直接求肯定TLE，但是如果使用公式的话前几项精度不够，所以前106或107项10^6或10^7项
O（N）O（N）暴力跑出，然后使用高精度的调和级数求和公式，具体可以搜索维基百科或者百度欧拉常数
http://baike.baidu.com/link?url=BWFVuV7oshbt5k7Z2HhvmV84MlXGg2bBE0_MJsQ9ZOJLI8o773s5-Z6k6xK7csGekpFwn0kn539eYbgY-lUDeq
最后的三个公式是表示欧拉常数，y=Hn−ln n+ln(n+1)2−16n(n+1)+130n2(n+1)2y = H_n - \frac{ln{\space}n+ln(n+1)}{2} - \frac{1}{6n(n+1)} + \frac{1}{30n^2(n+1)^2} (Hn为调和级数前n项的和)(H_n 为调和级数前n项的和)

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cstring>
#include <string>
#include <vector>
#include <cmath>
#include <set>
#define MOD 998244353
using namespace std;
typedef unsigned long long ull;
typedef long long ll;

/*---------------------------head files----------------------------------*/
const double euler = 0.577215664901532860606512090082;
double arr[1000009];

void init()
{
    arr[1] = 1.0;
    for (int i = 2 ; i <= 1000000 ; i ++)
    {
        arr[i] = arr[i-1] + 1.0 / i ;
    }
}

int main()
{
    init();
    int T,k=1;
    ll n;
    scanf("%d",&T);
    while (T--)
    {
        scanf("%lld",&n);
        printf("Case %d: ",k++);
        if (n<=1000000)
            printf("%.8f\n",arr[n]);
        else
        {
            double ans = (log(n) + log(n+1))/2.0;
            double x1 = 1.0;
            x1 = x1 / 6.0 / n / (n+1);
            double x2 = x1 ;
            x2 = x2 /5.0 / n / (n+1);
            ans = ans - x1 + x2 ;
            printf("%.10f\n",ans+euler);
        }
    }
}

Posted on Edited on In ,

题目链接：
http://acm.hust.edu.cn/vjudge/contest/70017#problem/Z

题目大意：
有些数既是一个数的p次方，又是另一个数的q次方，称这样的数为Super Power，没有输入，输出所有这样的数

分析：
显而易见，满足可以写成两个以上的数不同次方的数，它的次方数必然是个合数，同时由于最小的合数是4，所以最大的底数是4264−1<216^4\sqrt{2^{64}-1}<2^{16}
至多65536个数，每个数至多64次幂，O(106)O(10^6)，不会T
为了防止重复，最好使用集合来存数，最后用迭代器输出集合，注意循环从2开始的话需要在一开始向集合里插入一个1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<map>
#include<set>
#include <algorithm>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int maxn = 65;
ll notprime[maxn];
int tot ;
bool num[maxn];
set<ull> ans;

ull quickpow(ll a,ll n)
{
    ull ans=1;
    while(n)
    {
        if (n&1)
            ans = ans * a;
        a = a * a ;
        n >>= 1;
    }
    return ans;
}


void init()
{
    int i,j;
    for ( int i = 2; i <= maxn ; i ++ )
        if (num[i])
            notprime[++tot]=i;
        else
            for (int j = 2 *i ; j <= maxn ; j += i )
                num[j]=true;
    ans.insert(1);
    for (int i = 2 ; i < (1<<16);i ++)
    {
        int maxx = ceil(64*log(2.0)/log(i*1.0));
        for (int j = 4 ; j < maxx ; j ++)
        {
            if (num[j])
                ans.insert(quickpow(i,j));
        }
    }
}


int main()
{
    init();
    int n;
    for (auto i : ans)
    {
        printf("%llu\n",i);
    }

}

Posted on Edited on In ,

题目链接：
http://acm.hdu.edu.cn/showproblem.php?pid=6050

题目大意：
对Fx,yF_{x,y}给出三个定义式，求Fm,1%1000000007F_{m,1}\%1000000007之后的值

分析：
根据$F_{1,i} = F_{1,i-1} + 2*F_{1,i-2} $可以看出 F1,i−2F1,i−1F_{1,i} - 2F_{1,i-1}成等比，然后迭代即可求得F1,iF_{1,i}的通项，然后求和便是F2,1F_{2,1}的值，之后发现，然后再对第二行的前n个数求和，得到F3,1F_{3,1}即可发现答案，或者打表寻找在不同的n下，从F2,1F_{2,1}到F3,1F_{3,1}及后面多个数的变化即可发现

Fm,1={（2n−1)∗F2,1   n is even(2n−1)∗Fm−1,1−S1,n−1   n is oddF_{m,1} =\begin{cases} &（2^n-1)*F_{2,1} \space\space\space n \space is\space even\\ & (2^n-1)*F_{m-1,1}-S_{1,n-1} \space\space\space n\space is \space odd\end{cases}

n为奇数时减去的常数也可以由打表找出，打表发现n=3n=3时，F3,1=(23−1)∗F2,1−2F_{3,1} = (2^3 -1)*F_{2,1} - 2 , n=5n=5时，F3,1=(25−1)∗F2,1−10F_{3,1} = (2^5-1)*F_{2,1} - 10 ,而n=7n=7时，常数为42，可以发现C(n−1)/2=4∗C(n−3]/2+2C_{(n-1)/2} = 4*C_{(n-3]/2}+2继续拆解构造数列通项式即可得到常数的表达式，然后快速幂即可得到答案，中间分数用逆元处理

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
#include <bits/stdc++.h>


using namespace std;

typedef long long ll;

const int maxn = 2e5+200;
const int mod = 1e9+7;

ll n,m;


ll f[200],arr[20][1000];

ll quickpow(ll a,ll n)
{
    ll res = 1;
    while (n)
    {
        if (n&1)    res = res*a%mod;
        a = a*a %mod;
        n >>= 1;
    }
    return res;
}



int main() {
    int T,t=1;
    ll rst = quickpow(3,mod-2);
    ll rss = quickpow(2,mod-2);
    scanf("%d",&T);

    while (T--)
    {
        scanf("%lld%lld",&n,&m);
        ll tnp = quickpow(2,n);
        ll fsone = ((tnp*2-2+(n&1))*rst)%mod , p =tnp - 1;
        ll rs = quickpow(p-1,mod-2);
        if (m==1)
            printf("1\n");
        else   if (n&1)
        {
            ll d = (tnp-2)%mod*rst%mod;
            ll ans = (fsone-d*rs%mod+mod)%mod*quickpow(p,m-2)%mod+d*rs%mod;
            printf("%lld\n",ans%mod);
        }
        else
        {
            ll ans = fsone*quickpow(tnp-1,m-2)%mod;
            printf("%lld\n",ans);
        }

    }

    return 0;
}

Posted on Edited on In ,

题目链接：
https://vjudge.net/contest/70325#problem/A

题目大意：
给定两个数字串，第一个为待匹配串，第二个为模式串，求模式串第一个在待匹配串中出现的下标，没有则返回-1

分析：
简单修改KMP模板即可应用到数字串匹配上

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

int a[1000009],b[10009];
int n,m,Next[10009];
int pos;


void cover()
{
    int i  , j = 0;
    Next[0] = Next[1]  = 0;
    for (int i = 1; i < m ; i ++)
    {
        while (j&&b[i]!=b[j]) j = Next[j];
        if (b[i]==b[j]) ++j;
        Next[i+1] = j;
    }
    return ;
}

int kmp()
{
    int j = 0;
    for (int i = 0 ; i < n ; i ++)
    {
        while (j&&a[i]!=b[j]) j = Next[j];
        if (a[i]==b[j]){
            if (j==m-1)
               return i - j + 1;
            ++j;
        }
    }
    return -1;
}


int main(){
    int T;
    scanf("%d",&T);
    while (T--)
    {
        scanf("%d%d",&n,&m);
        for (int i = 0 ; i < n ; i ++)
            scanf("%d",&a[i]);
        for (int i = 0 ; i < m ; i ++)
            scanf("%d",&b[i]);
        cover();
        printf("%d\n",kmp());
    }
}

Posted on Edited on In ,

题目链接：
http://poj.org/problem?id=3744

题目大意：
一个人，一开始处于位置1，在n个位置上有地雷，不能接触，每次人有pp概率向前走一步，有1−p1-p概率向前跳两步，请问安全走过雷区的概率是多少,地雷位置x∈[1,100000000]x\in[1, 100000000]

分析：
dp[i]表示走到i处的概率的话，可以很快推出

dp[i]=p∗dp[i−1]+(1−p)∗dp[i−2]dp[i] = p*dp[i-1] + (1-p)*dp[i-2]

即dp[i]dp[i]是由dp[i−1]dp[i-1] 与dp[i−2]dp[i-2]贡献得到，那么从1开始，向上不断贡献，遇到地雷位置跳过，然后走到a[n]+1a[n]+1位置的概率即是答案，但是根据题意a[n]+1a[n]+1过大，且有多组数据，所有需要优化。

可以发现在每段中，情况几乎都相同，而且dp转移式很自然的能想到斐波那契F[i]=F[i−1]+F[i−2]F[i] = F[i-1] + F[i-2] ，所以这题可以用矩阵快速幂计算每一段的概率值，下一段的起点即是之前一个地雷的下一个位置，分别计算不走到各地雷的概率并作积即可

注意：

  • 地雷位置可以为1，即起点
  • 地雷读入为乱序
  • 地雷可能有重合
  • 地雷之间可能连续，即出现2，3连续位置的地雷

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
#include<stdio.h>
#include<algorithm>
#include<iostream>
#include<string.h>
#include<math.h>
using namespace std;

typedef long long ll;

const int maxn = 207;
const int mod = 1000000007;
const int Mod = 1000;
struct mat{
    int r,c;
    double m[10][10];
    mat(){}
    mat(int _r,int _c):r(_r),c(_c){};
};


void init(mat &a){
    memset(a.m,0,sizeof(a.m));
}

mat mul(mat a, mat b){
    mat tmp(a.r,b.c);

    for (int i = 1 ; i <= tmp.r; i ++)
    {
        for (int j = 1 ; j <= tmp.c ;j ++){
            tmp.m[i][j] = 0;
            for (int k =1 ; k <= a.c ; k ++){
                tmp.m[i][j] = (tmp.m[i][j]+(a.m[i][k]*b.m[k][j]));
            }
        }
    }
    return tmp;
}


mat QP(mat a ,int n){
    mat ans(a.r,a.r),tmp(a.r,a.r);
    memcpy(tmp.m,a.m,sizeof(tmp.m));
    init(ans);
    for (int i = 1 ; i <= ans.r ; i ++)
    {
        ans.m[i][i] = 1;
    }
    while (n){
        if (n&1)    ans = mul(ans,tmp);
        n >>= 1;
        tmp = mul(tmp,tmp);
    }
    return ans;
}


void print(mat a){
    for (int i = 1 ; i <= a.r ;++ i){
        for (int j = 1 ; j <= a.c ; ++j){
            printf("%f",a.m[i][j]);
            if (j==a.c) putchar('\n');
            else  putchar(' ');
        }
    }
}

int n;
double p;
int arr[maxn];
double dp[100000009];

int main()
{
    while (~scanf("%d%lf",&n,&p))
    {
        mat a(2,2);
        a.m[1][1] = p;
        a.m[1][2] = 1;
        a.m[2][1] = 1-p;
        a.m[2][2] = 0;
        for (int i =1 ; i <= n ; i ++)
            scanf("%d",&arr[i]);
        sort(arr+1,arr+n+1);
        if (arr[1] == 1)
            printf("%.7f\n",0);
        else
        {
            double t = 1;
            mat ans = QP(a,arr[1]-1);
            t *= (1-ans.m[1][1]);
            int f = 1;
            for (int i = 2 ; i <= n ; i ++)
            {

                if (arr[i]==arr[i-1])
                    continue;
                if (arr[i]-arr[i-1]==1)
                {
                    f = 0;
                    printf("%.7f\n",0);
                    break;
                }
                ans = QP(a,arr[i]-arr[i-1]-1);
                t *= (1-ans.m[1][1]);
            }
            if (f)
                printf("%.7f\n",t);
        }

    }
    return 0;
}

Posted on Edited on In ,

题目链接：
http://acm.hdu.edu.cn/showproblem.php?pid=5902

题目大意：
给定n个数，每次操作可以取其中3个，选择其中两个作gcd运算，并向原串中添加两次gcd结果，即a,b,c三个数，可取a,b作gcd(a,b)=g，将g写入原序列两次，求进行n-2次操作后，留下的数可能是什么

分析：
每次操作，取三个数，放回两个数，同时放回的数必定是原序列中数两两gcd，或gcd的结果再多次gcd，则此时题意已很明了，只需从前向后扫，加当前数与集合中所有数gcd的结果也加入集合中，最后输出集合中所有数即可得到答案，此外，要注意，由于一开始要丢弃一个数，最后得到的答案中，所有数的gcd需要特判，如果在循环中该值只出现了一次，则要删除，因为循环本身会产生该值，但这是无法出现的

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <string>
using namespace std;

int gcd(int a, int b)
{
    return b==0? a : gcd(b,a%b);
}

int arr[1000];
map<int,int> mp,ms;
map<int,int>::iterator it;
int n;
int main()
{
    int T;
    int cnt;
    scanf("%d",&T);
    while (T--)
    {
        int cnt=0,g;
        scanf("%d",&n);
        for (int i = 0 ; i < n ; i++)
        {
            scanf("%d",&arr[i]);
            if (i==0)
                g= arr[i];
            else
                g = gcd(g,arr[i]);
        }
        if (n==3)
        {
            mp.clear();
            mp[gcd(arr[0],arr[1])]++;
            mp[gcd(arr[1],arr[2])]++;
            mp[gcd(arr[2],arr[0])]++;
            for (it = mp.begin();it != mp.end() ; it ++)
            {
                if (it->second)
                {
                    if (it==mp.begin())
                        printf("%d",*it);
                    else
                        printf(" %d",*it);
                }
            }
            putchar('\n');
        }
        else
        {
            mp.clear();
            ms.clear();
            mp[gcd(arr[0],arr[1])]++;
            for (int i = 2 ; i < n ; i ++)
            {
                ms.clear();
                for (it = mp.begin() ; it != mp.end() ; it ++)
                {
                    ms[gcd(it->first,arr[i])]++;
                }
                for (int j = 0 ; j < i ; j ++)
                    mp[gcd(arr[i],arr[j])]++;
                for (it = ms.begin() ; it != ms.end() ; it ++)
                {
                    mp[it->first]++;
                }
            }
            mp[g]--;
            bool first = true;
            for (it = mp.begin();it != mp.end() ; it ++)
            {
                if (it->second)
                {
                    if (first)
                    {
                        printf("%d",it->first);
                        first = false;
                    }
                    else
                        printf(" %d",it->first);
                }
            }
            putchar('\n');

        }
    }

}