题目描述：

vjudge

题解：

STO ljx OTZ

下面这个算法是这位贡献的。

---

不妨将删去改为加入。

那么对于$n=p^k$，即只有一个质因子的$n$来说，若$i$已选，那么$i+n/p$、$i+2*n/p$……都必选。

这个先感性理解一下。

根据这个可以$O(n)$出解。

再看$n=p1^{k1}*p2^{k2}$，即有两个质因子。

对于已选点$i$有两种选择，一种是$i+n/p1$、$i+2*n/p1$……都选，另一种是$i+n/p2$、$i+2*n/p2$……都选。

这个可以将原来的$n$个点分成$n/p1/p2$组，每组都两种选择，即要么分$p1$小组，要么分$p2$小组。

时间复杂度貌似也是$O(n)$？？！

代码：

#include
#include
#include
using namespace std;
const int N = ;
template
inline void read(T&x)
{
T f = ,c = ;char ch=getchar();
while(ch<''||ch>''){if(ch=='-')f=-;ch=getchar();}
while(ch>=''&&ch<=''){c=c*+ch-'';ch=getchar();}
x = f*c;
}
int n,k,m[],c;
bool vis[N],vis1[N],vis2[N];
void init()
{
int n0 = n;
for(int i=;i*i<=n0;i++)if(n0%i==)
{
m[++c] = i;
while(n0%i==)n0/=i;
}
if(n0!=)m[++c]=n0;
}
int cxk(int x){return x<n?x:x%n;}
int sta[N],tl;
int main()
{
read(n),read(k);init();
if(c==)
{
int ans = ;
for(int x,i=;i<=k;i++)
{
read(x);x--;vis[x]=;
if(!vis1[x])
{
vis1[x] = ;ans += m[];
int j = cxk(x+n/m[]);
while(j!=x)vis1[j]=,j=cxk(j+n/m[]);
}
}
if(ans==n)puts("-1");
else
{
printf("%d\n",ans-k);
for(int i=;i<n;i++)if(!vis[i]&&vis1[i])
printf("%d ",i+);
puts("");
}
return ;
}else
{
for(int x,i=;i<=k;i++)
{
read(x),x--,vis[x]=;
if(!vis1[x])
{
for(int j=x,k=;k<=m[];j=cxk(j+n/m[]),k++)vis1[j]=;
}
if(!vis2[x])
{
for(int j=x,k=;k<=m[];j=cxk(j+n/m[]),k++)vis2[j]=;
}
}
for(int i=;i<n/m[]/m[];i++)
{
int c1 = ,c2 = ;
for(int j=i,k=;k<=m[]*m[];j=cxk(j+n/m[]/m[]),k++)
{
if(!vis[j]&&vis1[j])c1++;
if(!vis[j]&&vis2[j])c2++;
}
if(c1<c2)
{
for(int j=i,k=;k<=m[]*m[];j=cxk(j+n/m[]/m[]),k++)
if(!vis[j]&&vis1[j])sta[++tl]=j+;
}else
{
for(int j=i,k=;k<=m[]*m[];j=cxk(j+n/m[]/m[]),k++)
if(!vis[j]&&vis2[j])sta[++tl]=j+;
}
}
if(tl+k==n)puts("-1");
else
{
sort(sta+,sta++tl);
printf("%d\n",tl);
for(int i=;i<=tl;i++)
printf("%d ",sta[i]);
puts("");
}
}
return ;
}