首页 > 资讯 > 其他 > 正文

Codeforces Round #447 (Div. 2) C. Marco and GCD Sequence 构造“编程题”

17-11-22 来源：[db:作者]

收藏我要投稿

题意：

有一段序列，对他的所有的子序列的gcd放入set里面，然后把这个set给你，问是否合法，若合法，把原序列构造出来

思路：

开始我想错了，以为任意的连续子序列的gcd一定存在于set中，其实不然，例如原序列（2，12，2，18）-》（2，12，18）

但是我们能确定的是，对于给定的set，只要最小的那个数是所有数的因子，那么我们就可以构造一个满足条件的序列也就是原序列；

把最小的那个数插到给定序列中间就行了；

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#define PI acos(-1.0)
#define in freopen("in.txt", "r", stdin)
#define out freopen("out.txt", "w", stdout)

using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int maxn = 1000 + 7, maxd = 670000 + 7, mod = 1e9 + 7;
const int INF = 0x7f7f7f7f;

int n;
ll a[maxn];

int main() {

    scanf("%d", &n);
    for(int i = 1; i <= n; ++i) {
        scanf("%lld", &a[i]);
    }
    int i;
    for(i = 1; i <= n; ++i)
        if(a[i] % a[1]) break;
    if(i <= n) puts("-1");
    else {
        printf("%d\n%lld", n*2-1, a[1]);
        for(int i = 2; i <= n; ++i)
            printf(" %lld %lld", a[1], a[i]);
    }

    return 0;
}

点击复制链接与好友分享!回本站首页