题目
传送门 to luogu
思路
一开始想的二分答案。不过这个也不是完全不可取。至少为正解提供了思路。
假如我们需要
gcd
≤
d
\gcd\le d
gcd≤d ，那么
∀
x
≤
d
\forall x\le d
∀x≤d 都可以直接加入，毕竟
gcd
(
a
,
b
)
≤
min
(
a
,
b
)
\gcd(a,b)\le\min(a,b)
gcd(a,b)≤min(a,b) 。但是
∀
x
>
d
\forall x>d
∀x>d 都有
x
x
x 的倍数最多出现一次，否则至少有一个
x
x
x 的
gcd
\gcd
gcd 。
对于
k
x
kx
kx ，就没有 “
k
x
kx
kx 的倍数最多选一个” 的限制，因为 “
x
x
x 的倍数最多选一个” 已经把它包含了。
那么我们还剩下多少个限制呢？先不告诉你，我先告诉你答案怎么算。假设剩下
r
r
r 个限制，那么最多只可能拿
r
r
r 个数字，因为这
r
r
r 个限制已经涵盖了所有数字。能不能拿到这个峰值呢？当然可以，就是尽量拿小的即可。举栗子，
d
=
3
d=3
d=3 时，
4
4
4 的倍数最多出现一次，那么就拿
4
4
4 即可，就一定不会对别的限制产生影响。
于是问题转化为怎么求独立的限制。显然限制 “
x
x
x 的倍数最多出现一次” 会被
x
x
x 的因子给踢掉。也就是说，
∃
k
∣
x
,
d
<
k
\exist k|x,\;d<k
∃k∣x,d<k 则
x
x
x 嗝屁。肯定只有最大的
k
k
k 有用。也就是求
x
x
x 的最大真因子。这个可以用
x
x
x 除以
x
x
x 的最小质因数得到。欧拉筛即可。
然后呢？设
x
x
x 的最大真因子是
y
y
y ，那么我们知道，
d
≥
y
d\ge y
d≥y 则
x
x
x 是可用的。这可以直接差分。
现在我们求出了
∀
d
,
gcd
<
d
\forall d,\;\gcd<d
∀d,gcd<d 时的最大集合，还原回
I
k
I_k
Ik 不是轻而易举吗？
代码
#include <cstdio>
#include <iostream>
#include <vector>
using namespace std
;
typedef long long int_
;
inline int readint(){
int a
= 0; char c
= getchar(), f
= 1;
for(; c
<'0'||c
>'9'; c
=getchar())
if(c
== '-') f
= -f
;
for(; '0'<=c
&&c
<='9'; c
=getchar())
a
= (a
<<3)+(a
<<1)+(c
^48);
return a
*f
;
}
inline void writeint(int x
){
if(x
> 9) writeint(x
/10);
putchar((x
%10)^48);
}
const int MaxN
= 500005;
bool isPrime
[MaxN
];
int least
[MaxN
];
vector
< int > primes
;
int sievePrime(int n
){
for(int i
=2; i
<=n
; ++i
)
isPrime
[i
] = true;
int len
= 0; primes
.clear();
for(int i
=2; i
<=n
; ++i
){
if(isPrime
[i
]){
primes
.push_back(i
);
least
[i
] = i
, ++ len
;
}
for(int j
=0; j
<len
; ++j
){
if(1ll*i
*primes
[j
] > n
)
break;
isPrime
[i
*primes
[j
]] = 0;
least
[i
*primes
[j
]]
= primes
[j
];
if(i
%primes
[j
] == 0)
break;
}
}
return len
;
}
int cnt
[MaxN
];
int main(){
int n
= readint();
sievePrime(n
), least
[1] = 1;
for(int i
=1; i
<=n
; ++i
)
++ cnt
[i
/least
[i
]];
for(int i
=1,t
=0,p
=2; i
<=n
; ++i
){
t
+= cnt
[i
];
for(; p
<=t
; ++p
)
printf("%d ",i
);
}
return 0;
}
