Prime Graph

发表于 分类于 ，

    给出n个点，求一个图。

    要求这张图满足：

    1. 图是简单无向图（即没有重边和自环）

    2. 点的编号为1~n

    3. 图的边数是素数

    4. 每个点的度都是素数 （0,1不是素数）

    注意：图可以不连通，给出任意一张符合上述要求的图即可。

Prime Graph

Created by LXC on Tue Mar 5 19:02:31 2024

https://codeforces.com/problemset/problem/1178/D

ranting: 1500

tag: constructive algorithms, greedy, math, number theory

problem

给出n个点，求一个图。
要求这张图满足：

  1. 图是简单无向图（即没有重边和自环）
  2. 点的编号为1~n
  3. 图的边数是素数
  4. 每个点的度都是素数 （0,1不是素数）

注意：图可以不连通，给出任意一张符合上述要求的图即可。

solution

先找到大于等于n的最小质数p。

显然$p-n < \lfloor\frac{n}{2}\rfloor$

那么我们先让n个点成环，花费n条边，每个点的度为2

对于多的$p-n$条边，可以让$i$连接$i+\lfloor\frac{n}{2}\rfloor$,$i \in [1, p-n]$

code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63

#include <bits/stdc++.h>
#define SINGLE_INPUT
#define ll long long
#define ull unsigned long long
#define N 500005
#define MOD 998244353
using namespace std;

template<class t,class u> ostream& operator<<(ostream& os,const pair<t,u>& p) {
    return os<<'['<<p.first<<", "<<p.second<<']';
}
template<class t> ostream& operator<<(ostream& os,const vector<t>& v) {
    os<<'['; int s = 1;
    for(auto e:v) { if (s) s = 0; else os << ", "; os << e; }
    return os<<']';
}
template<class t,class u> ostream& operator<<(ostream& os,const map<t,u>& mp){
    os<<'{'; int s = 1;
    for(auto [x,y]:mp) { if (s) s = 0; else os << ", "; os<<x<<": "<<y; }
    return os<<'}';
}

int isp(int x) {
    for (int i=2; i*i<=x; i++) {
        if (x%i == 0) return false;
    }
    return true;
}

void sol() {
    int n;
    cin >> n;
    int b = n/2;
    int p = n;
    while (!isp(p)) p++;
    cout << p << "\n";
    cout << "1 " << n << "\n";
    for (int i=2; i<=n; i++) {
        cout << i << " " << i-1 << "\n";
    }
    for (int i=1; i<=p-n; i++) {
        cout << i << " " << i+b << "\n";
    }
}

int main() {
    cout << setprecision(15) << fixed;
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
#ifndef SINGLE_INPUT
    int t;
    cin >> t;
    while (t--) {
        sol();
    }
#else
    sol();
#endif
    return 0;
}