[SDOI2017]遗忘的集合

时间:2021-07-02 04:29:41

[SDOI2017]遗忘的集合

综合了很多套路的题

一看就是完全背包

生成函数!

转化为连乘积形式

Pi....=F

求Ln!

降次才可以解方程

发现方程是:

f[i]=∑t|i : bool(t)*t/i

f[i]*i=∑t|i : bool(t)*t

f=g*1(*是狄利克雷卷积)

所以,g=f*1

构造得到的解是唯一的,所以其实解是唯一的。

O(nlogn)

(多项式全家桶多项式全家桶

int main(){
int n;rd(n);rd(mod);
Poly f;
f.resize(n+);
f[]=;
for(reg i=;i<=n;++i) rd(f[i]);
f=Ln(f);
for(reg i=;i<n+;++i) f[i]=mul(f[i],i);
sieve(n);
for(reg i=;i<=n;++i){
for(reg j=i;j<=n;j+=i){
g[j]=ad(g[j],mul(f[i],miu[j/i]));
}
}
int ans=;
for(reg i=;i<=n;++i){
if(g[i]) ++ans;
}
printf("%d\n",ans);
for(reg i=;i<=n;++i){
if(g[i]) printf("%d ",i);
}
return ;
}