题解：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。

$\therefore$ $p$ 是一个合数，矛盾。 得证。

到这里就有一个整体的思路了。

发现只能选这个质数，于是探讨一下选它满不满足其他的合数。

引理 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。

$\ \ \ \ \ \ \ \ \ \ \ \ \ $ 因此此时不可能到达 $p$。 所以该条件为充分必要条件，得证。

因此，只有一个质数的情况利用 引理3 以及 引理4 判断就好了。

代码

#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;
        }
    }
}