hdu 5902 GCD is Funny
2024-09-01 07:28:33
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?
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.
题意: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;
}
最新文章
- C++ 修饰名的格式探究
- HTTP状态代码含义
- linux for循环更改文件名字
- 阿里云中Centos下配置防火墙
- Scala 深入浅出实战经典 第41讲:List继承体系实现内幕和方法操作源码揭秘
- Android APP的安装路径
- mutable和volatile关键字
- codeforces629C Famil Door and Brackets (dp)
- Android 5.0 新特性
- CUGBACM_Summer_Tranning 组队赛解题报告
- python 弄github代码库列表
- [Warning] Aborted connection 11203 to db: &#39;ide&#39; user: &#39;nuc&#39; host: &#39;prd01.mb.com&#39; (Got an error writi
- 沉淀,再出发——手把手教你使用VirtualBox搭建含有三个虚拟节点的Hadoop集群
- 【Matplotlib-01】Python 绘图库 Matplotlib 入门教程
- 【C++】处理CSDN博文源码
- 结对开发项目--石家庄地铁web版
- 距离放弃python又近了一大步,而然只是第四天
- [LeetCode&;Python] Problem 704. Binary Search
- PHP中对象的本质
- Java面试题详解四:==和equals的去别