首页 > 代码库 > hdu 5902 GCD is Funny
hdu 5902 GCD is Funny
Problem Description
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?
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.
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.
题意:n个数每次选三个数删除,取其中两个数将gcd放回去两次,问最后剩的数可能是多少。
由于一开始取3个数要删掉一个,所以只要求n-1个的gcd。
#include <iostream>#include <cstring>#include <cstdio>using namespace std;int a[1010] , dp[1010];int gcd(int a , int b) { while(b) { int t = a % b; a = b; b = t; } return a;}int main(){ int t; scanf("%d" , &t); while(t--) { int n; scanf("%d" , &n); memset(dp , 0 , sizeof(dp)); for(int i = 1 ; i <= n ; i++) { scanf("%d" , &a[i]); } for(int i = 1 ; i <= n ; i++) { for(int j = i + 1 ; j <= n ; j++) { dp[gcd(a[i] , a[j])] = 1; } } int flag = 1; for(int i = 1 ; ; i++) { if(flag == 0 || i >= n - 2) break; flag = 0; for(int j = 1 ; j <= 1000 ; j++) { for(int l = 1 ; l <= n ; l++) { int gg = gcd(a[l] , j); if(dp[j] && !dp[gg]) { flag = 1; dp[gg] = 1; } } } } int temp = 0; for(int i = 1 ; i <= 1000 ; i++) { if(!temp) { if(dp[i]) { printf("%d" , i); temp = 1; } } else { if(dp[i]) printf(" %d" , i); } } printf("\n"); } return 0;}
hdu 5902 GCD is Funny
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。