[CF1178D] Prime Graph 的题解

题目大意

构造一个简单无向图，是所有的有度的点的度都是质数而且总共的边的数量的个数是质数。

思路

因为需要让所有的入度都为质数，所以我们可以找到两个相邻的质数 \(2,3\)，因为这样即使增加了一条边那么这个节点的度也是质数。

先将这个图构成一个巨大的环，接着如果所有的边数并不是质数，那么就随便找两个不相邻的点连边。

因为在 \(2000\) 以内，质数都是十分密集的，所以即使是最坏的情况，那么大于 \(2\cdot n\) 最近的质数也不会超过 \(n/2\)，直接将相距很远的点连边就可以了。

AC Code

#include<bits/stdc++.h>
using namespace std;
const int N=1005;
int n,a[N],s;
bool ck(int x){
	for(int i=2;i*i<=x;i++) if(x%i==0) return 0;
	return 1;
}
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cin>>n;
	while(!ck(s+n)) s++;
	cout<<n+s<<'\n';
	for(int i=1;i<=n;i++) cout<<i<<' '<<((i+1>n)?(i+1-n):(i+1))<<'\n';
	for(int i=1;i<=s;i++) cout<<i<<' '<<((i+n/2>n)?(i+n/2-n):(i+n/2))<<'\n';
	return 0;
}