题解：CF1684G Euclid Guess · Zhl2010 第二博客

CF1684G Euclid Guess。

不要看错题了，数对构成的序列 $p$ ，而不是序列两两进行。

首先，我们发现 $m$ 的限制很不好。

$x\le \frac{m}{3}$ 一定可以构造出来 $(3x,2x)$ 。
$x\ge \frac{m}{2}$ ，我们无法构造。
$\frac{m}{3}\le x\le \frac{m}{2}$ ，构造 $a\le \frac{m}{3}$ ， $b\ge \frac{m}{3}$ ，需要满足 $a+b*2\le m$ ，就是 $(a+b,a+b*2)$ （ $(a,a+b)$ 不行，因为会成为 $b \mod a$ ）。（后面成为大元素）

然后我们发现，大的元素一定会占用一个小的，对应上面就是 $b \mod a$ 。

然后小的元素可以被大的使用，也可以自我消耗，所以我们需要尽可能少用小的元素。

我们直接让 $a|b$ ，于是记录 $b$ ，然后进行 $(a+b,b)$ ，接着记录 $a$ ，然后进行 $(a,b)$ ，此时如果 $a|b$ 就结束了。

因为无论如何，我们都需要用到 $b$ 的因数（这是辗转相除，很妙）。

所以最后，我们对于每一个大元素 $b$ 需要匹配小元素，直接二分图匹配， $a|b$ 且 $a+b*2\le m$ 的有边。

所以题目里要求最后构造出来的总对数 $\le2*10^4$ 这个条件其实没用。

C++

#include<bits/stdc++.h>
using namespace std;
int n,m;
int t[1010];
int e[1010][1010];
int a[1010],aa=0,b[1010],bb=0;
int vis[1010],ma[1010];
int dfs(int x){
	for(int i=1;i<=aa;i++){
		if(!vis[i]&&e[i][x]){
			vis[i]=1;
			if(!ma[i]||dfs(ma[i])){
				ma[i]=x;
				return 1;
			}
		}
	}
	return 0;
}
 

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		cin>>t[i];
		if(t[i]*2>m)return cout<<-1<<endl,0;
		if(t[i]<=m/3)a[++aa]=t[i];
		else b[++bb]=t[i];
	}
	
	for(int i=1;i<=aa;i++){
		for(int j=1;j<=bb;j++){
			if(b[j]*2+a[i]<=m&&b[j]%a[i]==0)e[i][j]=1;
		}
	}
	for(int i=1;i<=bb;i++){
		for(int j=1;j<=aa;j++)vis[j]=0;
		if(!dfs(i)){
			cout<<-1<<endl;
			return 0;
		}
	} 
	
	cout<<aa<<endl;
	
	for(int i=1;i<=aa;i++){
		if(ma[i])cout<<a[i]+b[ma[i]]<<' '<<a[i]+b[ma[i]]*2<<endl;
		else cout<<a[i]*2<<' '<<a[i]*3<<endl;
	}
	
	return 0;
}