Codeforces 1178D. Prime Graph

传送门

首先每个点至少要有两条边连接

那么容易想到先保证这一点然后再慢慢加边

那么先构成一个环即可：$(1,2),(2,3),(3,4)...(n,1)$

然后考虑加边，发现一个点加一条边还是合法的，那么不妨直接 $(1,4),(2,5),(3,6)$ ，然后一旦边数为质数了就直接输出答案

那么现在问题就是能否保证在 $[n,n+\left \lfloor \frac {n-3} {2} \right \rfloor]$ 范围内一定有质数

打个表发现在 $n \in [3,1000]$ 内唯一不合法的只有 $n=4$，那么特判一下就行了......

官方题解竟然也是这个操作？？？没有证明的吗？？？

#include<iostream>

#include<cstdio>

#include<algorithm>

#include<cstring>

#include<cmath>

#include<vector>

using namespace std;

typedef long long ll;

inline int read()

{

    int x=,f=; char ch=getchar();

    while(ch<''||ch>'') { if(ch=='-') f=-; ch=getchar(); }

    while(ch>=''&&ch<='') { x=(x<<)+(x<<)+(ch^); ch=getchar(); }

    return x*f;

}

const int N=1e5+;

int n,m;

struct edge {

    int u,v;

    edge (int _u=,int _v=) { u=_u,v=_v; }

};

vector <edge> ans;

inline void ins(int u,int v) { ans.push_back(edge(u,v)); }

int pri[N],tot;

bool not_pri[N];

void pre()

{

    not_pri[]=;

    for(int i=;i<=*n;i++)

    {

        if(!not_pri[i]) pri[++tot]=i;

        for(int j=;j<=tot;j++)

        {

            ll g=1ll*i*pri[j]; if(g>*n) break;

            not_pri[g]=; if(i%pri[j]==) break;

        }

    }

}

int main()

{

    n=read(); pre();

    for(int i=;i<=n;i++) ins(i,i-);

    ins(,n); int now=n;

    if(n==) ins(,),now++;

    else

        for(int i=;i<=n-;i++)

        {

            if(!not_pri[now]) break;

            if(i&) ins(i,i+),now++;

        }

    if(not_pri[now]) { printf("-1\n"); return ; }

    printf("%d\n",now);

    for(auto E: ans) printf("%d %d\n",E.u,E.v);

    return ;

}