Codeforces Round #323 (Div. 2) C.GCD Table
The GCD table G of size n × n for an array of positive integers a of length n is defined by formula
![](http://codeforces.com/predownloaded/c4/11/c41174b207b1e8f3f5b51c6c0b2a1a479f9fd5ac.png)
Let us remind you that the greatest common divisor (GCD) of two positive integers x and y is the greatest integer that is divisor of both xand y, it is denoted as . For example, for array a = {4, 3, 6, 2} of length 4 the GCD table will look as follows:
![](http://codeforces.com/predownloaded/30/61/306134769278f09384ca40efc6a5d981b18f3bb9.png)
Given all the numbers of the GCD table G, restore array a.
Input
The first line contains number n (1 ≤ n ≤ 500) — the length of array a. The second line contains n2 space-separated numbers — the elements of the GCD table of G for array a.
All the numbers in the table are positive integers, not exceeding 109. Note that the elements are given in an arbitrary order. It is guaranteed that the set of the input data corresponds to some array a.
Output
In the single line print n positive integers — the elements of array a. If there are multiple possible solutions, you are allowed to print any of them.
ans[N]存放已经选中的数,即array中一定存在的数;
首先从X中找到最大的一个值aij,然后对ans[N]中的每一个数,得到g = gcd(aij, ans[i]),
由于table矩阵是对称的,所以从X中删除2个值为 g 的数值!
最后将aij放入ans中!不断重复此过程,知道ans中数字个数为n;
#include iostream #include cstring #include cstdio #include cmath #include map #include set #include algorithm #define N 505 using namespace std; int n; map int, int, greater int //key按照由大到小排序 int gcd(int a, int b){ return b==0 ? a : gcd(b, a%b); int ans[N]; int main(){ cin n; int nn = n*n; for(int i=0; i ++i){ int x; cin x; mp[x]++; int len = 0; for(map int, int, greater int ::iterator it=mp.begin(); it!=mp.end();){ if(it- second == 0){//不为0,说明这个数还是array中的数字 ++it; continue; --it- second; for(int i=0; i ++i){ int gcdn = gcd(it- first, ans[i]); mp[gcdn]-=2; ans[len++] = it- first; for(int i=0; i ++i){ if(i!=0) cout " "; cout ans[i]; cout endl; return 0; }
Codeforces Round #723 (Div. 2)B. I Hate 1111 Description You are given an integer x. Can you make x by summing up some number of 11,111,1111,11111,…? (You can use any number among them any number of times). For instance, 33=11+11+11 144=111+11+11+11
相关文章
- element table_elementuos8
- 【已解决】ShardingSphere 使用记录,ShardingException: Can not update sharding key, logic table: [user_log]解决
- ORA-23360: only one materialized view for master table “string” can be created ORACLE 报错 故障修复 远程处理
- ORA-24072: cannot execute MIGRATE_QUEUE_TABLE procedure; must own queue table ORACLE 报错 故障修复 远程处理
- ORA-41701: conditions table with a rule class association cannot be truncated or dropped ORACLE 报错 故障修复 远程处理
- ORA-41705: conditions table cannot be dropped with DROP TABLE command ORACLE 报错 故障修复 远程处理
- ORA-42041: cannot online redefine table “string”.”string” with nested table columns ORACLE 报错 故障修复 远程处理
- ORA-55610: Invalid DDL statement on history-tracked table ORACLE 报错 故障修复 远程处理
- MySQL Error number: MY-010358; Symbol: ER_TZ_OOM_LOADING_LEAP_SECOND_TABLE; SQLSTATE: HY000 报错 故障修复 远程处理
- SQLServer 错误 7923 Table TABLE 对象 ID O_ID。 故障 处理 修复 支持远程
- MySQL Error number: MY-011060; Symbol: ER_DD_UPGRADE_TABLE_INTACT_ERROR; SQLSTATE: HY000 报错 故障修复 远程处理
- ORA-13114: [string]_NODE$ table does not exist ORACLE 报错 故障修复 远程处理
- ORA-14095: ALTER TABLE EXCHANGE requires a non-partitioned, non-clustered table ORACLE 报错 故障修复 远程处理
- ORA-14137: Table in partially dropped state, submit DROP TABLE PURGE ORACLE 报错 故障修复 远程处理
- ORA-14296: Table block size mismatch in ALTER TABLE EXCHANGE [SUB]PARTITION ORACLE 报错 故障修复 远程处理
- ORA-14457: disallowed Nested Table column in a Temporary table ORACLE 报错 故障修复 远程处理
- ORA-14756: Table is not partitioned by Interval method. ORACLE 报错 故障修复 远程处理
- ORA-16221: history table synchronization error ORACLE 报错 故障修复 远程处理
- MySQL Error number: MY-013240; Symbol: ER_SHARED_TABLESPACE_USED_BY_PARTITIONED_TABLE; SQLSTATE: HY000 报错 故障修复 远程处理
- MySQL中Table的创建修改和删除操作(mysql中table)
- table对象中的insertRow与deleteRow使用示例