CF2029E 题解

· · 题解

引理 1：2 可以生成任意合数。

证明：归纳法。显然 2 可以生成 4。

对于更大的合数 x=pq\ge 6(p,q>1)，假设 <x 的合数都能被生成。

如果 2|x，则 2|x-2，可以通过 x-2(\ge 4) 生成 x。

否则，p\ge 3，可通过 (p-1)q 生成 x。

引理 2：质数只能被它自己生成。

证明：假设 0<q<p 可以生成质数 p，则 p=q+d(d|q)，p=d(1+\frac{q}{d})，而 d\ge 2，所以 p 为合数，矛盾。

正解 Part 1：没有质数或有多于一种质数

由引理，没有质数时显然 2 满足条件，多于一种质数无解。

引理 3：偶数 x 可以被质数 p 生成的充要条件是 2p\le x。

证明：如果 2p\le x，那么由 p 生成 2p，由 2p 生成 2p+2,2p+4 一直到 x。

如果 2p>x，但是由 p （一次操作）只能生成 2p，且每次操作之后数单调增，所以不可能生成小于 2p 的数，就无法生成 x。

引理 4：设奇合数 x 的最小质因子为 p_0，则它可以被质数 p 生成的充要条件是 2p\le x-p_0。

证明：显然 x-p_0 为偶合数。

如果 2p\le x-p_0，那么由引理 3，p 可以生成 x-p_0，而 p_0|x，所以 p_0|x-p_0，可以生成 x。

如果 2p>x-p_0，那么 p 一步只能生成 2p，显然其 \neq x。

考虑可以通过一步操作生成 x 的数 y，说明 \exist d|y 使得 y+d=x，也就是说 \exist d|x 使得 y=x-d。

但 p_0 为 x 最小质因子，因此 d\ge p_0，y \le x-p_0。

所以对于任意可以生成 x 的数 z，满足 z\le y \le x-p_0。

然而 2p>x-p_0，说明它无法生成 x。

所以，p 无法生成 x。

正解 Part 2：判断一个质数的合法性

现在序列中有恰好一种质数，我们只需要判断其合法性即可。

根据引理 3 和引理 4，我们实际上只需要将质数 p 和 \frac{a_i}{2} 或是 \frac{a_i-p_i}{2} 比较（其中 p_i 为 a_i 最小质因子），可以用线性筛预处理这个值。

至此，我们在 O(n+V)（V 为值域）的时空复杂度内解决了这个问题。

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll N=400007;
ll T,n,a[N],prime[N],nP,x,rem[N];
bool ok[N];
void initPrime(ll n=N-1){
    ok[1]=1;
    for (int i=2;i<N;++i){
        if (!ok[i]) prime[++nP]=i;
        for (int j=1;j<=nP&&i*prime[j]<=n;++j){
            ll o=i*prime[j];
            ok[o]=1;
            if (o%2==0) rem[o]=o/2;
            else rem[o]=prime[j]*(i-1)/2;
            if (i%prime[j]==0) break;
        }
    }
}
int main(){
    initPrime();
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    cin>>T;
    while(T--){
        cin>>n;x=0;
        for (int i=1;i<=n;++i) cin>>a[i];
        for (int i=1;i<=n;++i) if (!ok[a[i]]){
            if (x==0||x==a[i]) x=a[i];else x=-1;
        }
        if (x==-1){
            cout<<x<<'\n';continue;
        }
        if (x==0){
            cout<<"2\n";continue;
        }
        for (int i=1;i<=n;++i) if (x!=a[i]&&rem[a[i]]<x) x=-1;
        cout<<x<<'\n';
    }
    return 0;
}