HDU-5902-GCD is Funny解题笔记
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
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
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 + ;
const ll MOD = 1e9 + ;
int GCD(int a, int b)
{
return b == ? a : GCD(b, a % b);
}
int num[MAXN];
int ans[MAXN];
int main()
{
ios::sync_with_stdio();
int t;
cin >> t;
while (t--)
{
memset(ans, , sizeof(ans));
int n;
cin >> n;
for (int i = ; i < n; i++)
cin >> num[i];
for (int i = ; i < n - ; i++)
for (int j = i + ; j < n; j++)
ans[GCD(num[i], num[j])] = ;
int cnt = n;
bool run = true;
while (cnt-- >= && run)
{
run = false;
for (int i = ; i <= ; i++)
if (ans[i])
for (int j = ; j < n; j++)
{
if (!ans[GCD(num[j], i)])
{
ans[GCD(num[j], i)] = ;
run = true;
}
}
}
bool flag = false;
for (int i = ; i <= ; i++)
{
if (ans[i])
{
if (!flag)
{
flag = true;
cout << i;
}
else
cout << ' ' << i;
}
}
cout << endl;
}
return ;
}
最新文章
- 备份了我的CSDN博客
- VS2015 调试时 编辑并继续不可用
- 一个十年java程序员的心得
- 图解JavaScript 继承
- Deep Learning 10_深度学习UFLDL教程:Convolution and Pooling_exercise(斯坦福大学深度学习教程)
- Json学习篇
- java 图片处理
- 在WP8上搭建cocos2d-x开发环境
- 跟我一起学习ASP.NET 4.5 MVC4.0(一)(转)
- JVM专题
- linux下svn客户端安装及环境配置(转)
- HIBERNATE 入门小案例
- Qt在表格中加入控件
- Oracle 11g 服务启动/关闭 及 DB dump 导入
- Movavi Video Editor 15 Plus(视频编辑软件) 中文版
- SqlServer查询Excel中的数据
- 编译安装spark 1.5.x(Building Spark)
- pycharm安装步骤
- For all entries in
- 学JS的心路历程-函式(二)arguments
热门文章
- SSL/TLS 配置
- sed &; awk &; grep 专题
- 25.python之面向对象
- 正基AP6212固件
- webhook功能概述
- lintcode入门37-算法实现
- 洛谷$P$2518 计数 $[HAOI2010]$ 数位$dp$
- shopnc 二次开发问题(一)
- selenium自动化测试入门 Alert/Confirm/Prompt 弹出窗口处理
- LibreOJ 6278. 数列分块入门 2 题解