CF894C Marco and GCD Sequence

gcd

The question ：

An interesting construction problem

I have an array , Put the... Of each interval gcd Put it in a collection , Give set , Try to restore the original sequence

Carelessness ：

1. The numbers in the original sequence should all come from this set .

2. For each interval ,gcd Not greater than their minimum .

Then find the total gcd, And divide each element by this gcd, If now in the sequence 1, It means that all elements in the set can be divided by an element belonging to the set , Then we just insert a public... In front of each element gcd As the original sequence .

If there is no 1, That means our public gcd Not in this collection , Then this set is insoluble .

code：

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll N=101000;
ll n;
ll mas[N];
vector<ll> q;
ll cnt=0;
ll sum=1;
ll gd=0;
void solve()
{
	bool f=0;
	for(int i=1;i<=n;++i)
	{
		mas[i]/=gd;
		//cout<<mas[i]<<" ";
		if(mas[i]==1) f=1;
	}
	if(!f)
	{
		cout<<-1;
		return;
	}
	for(int i=1;i<=n;++i)
	{
		q.push_back(gd);
		q.push_back(mas[i]*gd);
	}
	cout<<q.size()<<endl;
	for(ll i:q) cout<<i<<" "; 
}
int main()
{
	cin>>n;
	for(int i=1;i<=n;++i)
	{
		cin>>mas[i];
		gd=__gcd(gd,mas[i]);
	}
	solve();
	return 0;
}