题解：CF2029E Common Generator

前言

本文主要参考了 这篇题解。

思路

引理 1：对于合数来说，$2$ 永远是满足条件的生成器。

证明：采用归纳法。
假设当前数为 $x$，小于 $x$ 的合数都满足条件，那么可以分两种情况：

• 对于偶合数，有：$2 \mid x$，那显然也有 $2 \mid (x-2)$，因此可以从 $x-2$ 转移过来。
• 对于奇合数，$x$ 也一定可以表示成 $x=pq$ 的形式（其中 $p$ 为最小的质因子）。
  因为 $x$ 为合数，所以 $q>1$（根据因数定理可知）。
  又因为 $x$ 不为偶数，所以不含有偶数因子，那么 $p \ge 3$。所以，$(p-1)q$ 也一定是一个合数。根据前置的条件，$(p-1)q$ 可以被表示，而 $p$ 是质数，所以 $pq$ 即 $x$ 可以表示为 $(p-1)q + p$。因此能被表示。

得证。

引理 2：质数只能由本身来生成。

证明：反证法。
如果一个质数 $p$ 可以由 $q$ 生成而来（$q<p$），那么一定有：$p=q+d$，其中 $d \mid q$ 并且 $d > 1$。

因为 $q=n \times d$，所以：$p = q + d = (n+1)d$。
$\because$ $n+1 \ge 2$ 且 $d \ge 2$。
$\therefore$ $p$ 是一个合数，矛盾。

得证。

• 序列中没有质数。根据 引理 1，直接输出 $2$ 即可。
• 序列中有不同的质数。根据 引理 2，不管选择哪一个都不能满足所有的数，因此无解。
• 序列中有且只有一个质数。还要再讨论一下。

引理 3：对于偶合数 $p$，质数 $q$ 能表示它必须满足 $2q \le p$。

证明：考虑是否为充分必要条件。

充分性：若 $2q \le p$，根据 引理 2 可知，$q$ 只能一步到达 $2q$。因为 $2|2q$，所以$2|(p-2q)$。因此后面只要全用 $2$ 就好了。

必要性：若 $2q > p$，因为 $q$ 只有先到 $2q$，而此时已经超过了 $p$，后面再操作只会变大，距离 $p$ 越来越远，不可能表示出 $q$。

因此，该条件是充分必要条件，得证。

引理 4：对于奇合数 $p$，质数 $q$ 能表示它必须满足 $2q \le p - low_p$。其中 $low_p$ 表示 $p$ 的最小质因子。

证明：还是考虑充分必要条件。

充分性：若 $2q \le p-low_p$，根据 引理 2 可知，$q$ 只能一步到达 $2q$。因为 $p$ 为奇数，所以 $low_p$ 也为奇数，所以 $p - low_p$ 为偶数。根据 引理 3 可知是合法的。

必要性：若 $2q > p-low_p$，因为 $q$ 只有先到 $2q$，可知此时 $2q \ne p$，因为奇偶性都不同。考虑能否到达 $p$。

$\ \ \ \ \ \ \ \ \ \ \ \ \$ 假设一个数 $x$ 可以一步到达 $q$，则跨越的数值 $d=q-x$ 一定为 $x$ 以及 $q$ 的因数。可知此时 $d \ge low_p$，所以当 $x \le p-low_p$ 才满足条件。可是$2q > p-low_p$，矛盾。

$\ \ \ \ \ \ \ \ \ \ \ \ \$ 因此此时不可能到达 $p$。

所以该条件为充分必要条件，得证。

代码

#include<iostream>
using namespace std;
int t,n;
const int N=5e5+10;
bool v[N];
int p[N],cnt;
int num[N];
void prime(){
	v[1]=1;
	for(int i=2;i<N;i++){
		if(!v[i]){
			p[++cnt]=i;
		}
		for(int j=1;j<=cnt&&i*p[j]<N;j++){
			int next=i*p[j];
			v[next]=1;
			if(next&1){
				num[next]=next-p[j];
			}else{
				num[next]=next;
			}
			if(i%p[j]==0){
				break;
			}
		}
	}
}

int a[N];
int main(){
	prime();
	cin>>t;
	while(t--){
		scanf("%d",&n);
		int x=0;
		for(int i=1;i<=n;i++){
			scanf("%d",&a[i]);
			if(x==-1){
				continue;
			}
			if(!v[a[i]]){
				if(!x){
					x=a[i];
				}else{
					x=-1;
				}
			}
		}
		if(x==-1){
			puts("-1");
		}else if(!x){
			puts("2");
		}else{
			for(int i=1;i<=n;i++){
				if(a[i]!=x&&num[a[i]]<2*x){
					x=-1;
					break;
				}
			}
			cout<<x<<endl;
		}
	}
}