HDU 5902：GCD is Funny （GCD）

HDU 5902：GCD is Funny （GCD）

GCD is Funny

Time Limit: 4000/2000 MS (Java/Others)    Memory Limit: 65536/65536 K (Java/Others)

Total Submission(s): 306    Accepted Submission(s): 65

Problem Description

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

Input

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. 我们只要在一开始丢掉了一个数, 考虑留下来两个数是x,x, 那么又选了另一个数y的话, 我们只要丢掉其中一个x就能获得了两个gcd(x,y), 也就是说接下来每次操作我们都有了一个额外的数用来丢弃, 且不会改变子集gcd的种类数.

所以我们可以先求出给出数字的两两GCD，然后用已有的GCD数列再一次与原数求一次GCD，依次输出.

AC代码：

#include#include#include#include#include#includeusing namespace std;int num[1100],a[1100];int gcd(int a,int b){ if(b==0)return a; return gcd(b,a%b);}int main(){ int T,n; cin>>T; while(T--) { cin>>n; memset(num,0,sizeof(num)); for(int i=0; i>a[i]; for(int i=0; i2) { flag=0; for(int i=1; i<=1000; i++) //对已有的GCD再次与数字进行GCD运算 if(num[i]) for(int j=0; j

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。