题目
官方题解&代码
题意：给定
n
n
n，表示集合
{
1
,
2
,
.
.
.
,
n
}
\{1,2,...,n\}
{1,2,...,n}，求出子集和大小为
k
k
k的
m
a
x
(
g
c
d
(
a
i
,
a
j
)
)
,
k
=
2
,
3
,
.
.
.
,
n
max(gcd(a_i,a_j)),k=2,3,...,n
max(gcd(ai,aj)),k=2,3,...,n
定义
A
=
a
1
,
a
2
,
.
.
.
,
a
k
A={a_1,a_2,...,a_k}
A=a1,a2,...,ak为一种可行的最小imperfection，如果对于
a
i
a_i
ai，它的一部分因子不在于集合
A
A
A中，那么我们可以用其中的一个因子代替
a
i
a_i
ai，此时集合大小不变，但他的imperfection可能变小。那么基于这个情况，我们可以假设集合
A
A
A任意元素的因子都在A中。定义
d
(
n
)
d(n)
d(n)为
n
n
n的除了他本身的最大因子
(
d
(
1
)
=
1
)
(d(1)=1)
(d(1)=1)。那么对于满足任意元素的因子都在集合中，的集合A，
m
a
x
(
a
i
,
a
j
)
=
m
a
x
(
d
(
a
i
)
)
max(a_i,a_j)=max(d(a_i))
max(ai,aj)=max(d(ai))。求出
d
(
∗
)
d(*)
d(∗)后，排序，即得所有的imperfection。
#include
using namespace std;
vector max_div;
void eratosthenes(int limit) {
max_div.assign(limit + 1, 0);
max_div[0] = limit + 10;
max_div[1] = 1;
for (int i = 2; i n;
eratosthenes(n);
sort(max_div.begin(), max_div.end());
for (int i = 1; i
关注
打赏
![]()
查看更多评论
