【Codeforces 582A】 GCD Table
2024-09-30 07:27:16
【题目链接】
【算法】
G中最大的数一定也是a中最大的数。
G中次大的数一定也是a中次大的数。
第三、第四可能是由最大和次大的gcd产生的
那么就不难想到下面的算法:
1. 令p为G中最大的数。在G中删除p,a中加入p。
2 . 对于a中的所有其他数(设为q),在G中删除2个gcd(p, q)。
3. 若G为空则结束;否则回到(1)。
【代码】
#include<bits/stdc++.h>
using namespace std;
#define MAXN 500 int i,N,x,k;
map<int,int> M;
int a[MAXN*MAXN];
vector<int> res; template <typename T> inline void read(T &x) {
int f = ; x = ;
char c = getchar();
for (; !isdigit(c); c = getchar()) { if (c == '-') f = -f; }
for (; isdigit(c); c = getchar()) x = (x << ) + (x << ) + c - '';
x *= f;
}
template <typename T> inline void write(T x) {
if (x < ) { putchar('-'); x = -x; }
if (x > ) write(x/);
putchar(x%+'');
}
template <typename T> inline void writeln(T x) {
write(x);
puts("");
} inline int gcd(int x,int y) { return !y ? x : gcd(y,x%y); } int main() { read(N);
for (i = ; i <= N * N; i++) {
read(a[i]);
M[a[i]]++;
}
sort(a+,a+N*N+);
for (i = N * N; i >= ; i--) {
if (!M[a[i]]) continue;
--M[a[i]];
for (k = ; k < res.size(); k++) M[gcd(a[i],res[k])] -= ;
res.push_back(a[i]);
}
for (i = ; i < res.size(); i++) {
write(res[i]);
if (i < res.size() - ) putchar(' ');
}
puts(""); return ;
}
最新文章
- [fiddler] 使用fiddler script自定义代理规则
- Android软件开发之ListView 详解【转】
- C语言题库的上机题
- C#.NET如何不序列化字段、属性
- phpcms 完美实现 导航栏当前栏目高亮
- 财务比率:ROE, 净利润增长率、毛利率、市盈率、PEG
- php随笔杂记(一)
- hdu4003Find Metal Mineral(树形DP)
- DateTime.ToString格式化日期,使用DateDiff方法获取日期时间的间隔数
- C#调用金数据API
- poj3264Balanced Lineup(RMQ)
- Best Financing(HD4833)
- Python之数学(math)和随机数(random)
- Markdown 编辑器使用指南
- Python基础学习(第一周)
- java 反射机制 观点
- Java实现栈之计算器
- js修改父子json格式成树状结构格式
- js用解构来定义变量并赋值
- 新版ADT创建项目时出现appcompat_v7的问题
热门文章
- delphi使用IdHTTP模拟提交页面方法总结
- HUNAN -11566 Graduation Examination(找规律)
- luogu P1080 国王游戏
- Ubuntu 16.04安装微信
- python解析网页中js动态添加的内容
- java之 ------ 文件的输入、输出(一)
- C#代码调用页面javascript函数
- 内存管理[5]通过 GetProcessHeaps 函数获取了当前进程的堆句柄列表
- 基于 orange(nginx+openresty) + docker 实现微服务 网关功能
- CS 和 BS 的区别和优缺点(转)