综合了很多套路的题
一看就是完全背包
生成函数!
转化为连乘积形式
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 ;
}