什么年代了还有人出高精题啊……
首先题目相当于构造一个正整数序列，将其中不互质的点连边后能连通。
考虑令序列首位为所有小于 \(N\) 的质数乘积，则根据更相减损术，除了第二个位置显然都能与首位连边。
然后我们发现并不是很好解决。
考虑令序列中心为所有小于等于 \(\frac N2\) 的质数乘积，则除了相邻的两个位置显然都能与中心连边。
可以牺牲两个质数的贡献来使这两个点连通。
但是牺牲了这两个质数之后又会有点不连通，于是再用几个大于 \(\frac N2\) 的质数使它们连通即可。
然后用 CRT 合并即可。
代码： 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
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
using namespace std;
const int N = 1e5;
const long long ANS[] = {2184,27829,27828,87890,87890,171054,171054,323510,127374,323510,151062,151062,151062,151061,151060,151059,151058,672540170262,672540170262,2101641443862,2101641443862,4152621523031};
int n,m;
int vis[N + 5],cnt,prime[N + 5];
int a[6],pos,l,r,mid;
struct bigint
{
static const int LEN = 10000;
static const int w = 1e9;
int a[LEN],len;
inline void clear()
{
memset(a,0,sizeof a),len = 0;
}
inline bigint(int x = 0)
{
clear();
for(a[len++] = x % w,x /= w;x;a[len++] = x % w,x /= w);
}
inline int operator%(const int &mod)
{
int ret = 0;
for(register int i = len - 1;~i;--i)
ret = ((long long)ret * w % mod + a[i] % mod) % mod;
return ret;
}
inline int &operator[](const int &x)
{
return a[x];
}
inline const int &operator[](const int &x) const
{
return a[x];
}
inline bigint &operator+=(const bigint &o)
{
len = max(len,o.len);
int k = 0;
for(register int i = 0;i < len;++i)
a[i] = a[i] + o[i] + k,k = a[i] / w,a[i] %= w;
for(;k;a[len++] = k % w,k /= w);
return *this;
}
inline bigint &operator-=(const bigint &o)
{
for(register int i = 0;i < len;++i)
a[i] -= o[i],a[i] < 0 && (a[i] += w,--a[i + 1]);
for(;!a[len - 1] && len > 1;--len);
return *this;
}
inline bigint operator*(const bigint &o)
{
bigint ret;
ret.len = len + o.len - 1;
__int128 k = 0;
for(register int i = 0;i < ret.len;ret[i] = k % w,k /= w,++i)
for(register int j = 0;j <= i;++j)
a[j] && o[i - j] && (k += (long long)a[j] * o[i - j],1);
for(;k;ret[ret.len++] = k % w,k /= w);
return ret;
}
inline bigint &operator*=(const bigint &o)
{
*this = *this * o;
return *this;
}
inline bool operator<(const bigint &o) const
{
if(len ^ o.len)
return len < o.len;
for(register int i = len - 1;~i;--i)
if(a[i] ^ o[i])
return a[i] < o[i];
return 0;
}
inline bool operator>=(const bigint &o) const
{
return !(*this < o);
}
void print()
{
printf("%d",a[len - 1]);
for(register int i = len - 2;~i;--i)
printf("%09d",a[i]);
}
} ans,mod = 1;
int fpow(int a,int b,int mod)
{
int ret = 1;
for(;b;b >>= 1)
(b & 1) && (ret = (long long)ret * a % mod),a = (long long)a * a % mod;
return ret;
}
void crt(int a,int p)
{
int w = (long long)(a - ans % p + p) * fpow(mod % p,p - 2,p) % p;
ans += mod * w,mod *= p;
for(;ans >= mod;ans -= mod);
}
bigint mul(int l,int r)
{
if(l == r)
return prime[l];
int mid = l + r >> 1;
return mul(l,mid) * mul(mid + 1,r);
}
int main()
{
freopen("teleports.in", "r", stdin),freopen("teleports.out", "w", stdout);
scanf("%d", &n);
if(n == 1)
{
puts("1");
return 0;
}
if(n <= 16)
{
puts("No solution");
return 0;
}
if(n <= 38)
{
printf("%lld\n",ANS[n - 17]);
return 0;
}
for(register int i = 2;i <= n;++i)
{
if(!vis[i])
prime[++cnt] = i;
for(register int j = 1;j <= cnt && i * prime[j] <= n;++j)
{
vis[i * prime[j]] = 1;
if(!(i % prime[j]))
break;
}
}
l = 1,r = cnt;
while(l <= r)
mid = l + r >> 1,
2 * prime[mid] < n ? (pos = mid,l = mid + 1) : (r = mid - 1);
mod = mul(1,pos - 2);
a[0] = prime[pos - 1],a[1] = prime[pos];
2 * prime[pos + 1] == n && (mod *= prime[++pos],1);
a[2] = prime[pos + 1],a[3] = prime[pos + 2],a[4] = prime[pos + 3],a[5] = prime[pos + 4];
crt(1,a[0]),crt(a[1] - 1,a[1]),crt(a[0],a[2]),crt(a[3] - a[0],a[3]),crt(a[1],a[4]),crt(a[5] - a[1],a[5]);
ans < (n + 1) / 2 && (ans += mod,1),(ans -= (n - 1) / 2).print();
}