P1027 叶片
题意简化
给出 n 个点的转盘，有一些点缺失，你需要再去掉一些点使得转盘重心稳定
那么其实就是要取出一些点和缺失的点构成一个稳定的转盘，这样的话所有取出的点肯定可以表示成多个正多边形
于是这道题可以简化为给定 (n) 个点，然后你用边数为 (n) 的约数的正多边形去框住所有的标记点，每个点最多被框一次，求框住的最少未标记点，那么未标记点最少其实就是总共框住的点数最少
（以下所说的多边形默认为正多边形，并且会出现 2 边形，默认它存在，退化为线）
最优选择
题目中数据范围说 (n) 最多有两个质因子
那么我们先考虑只有一个质因子怎么办
假设 (n=8) 那么我们可以用边数为 2 4 8 的多边形去框点，但其实只用边数为 2 的多边形去框就好了
因为 4 8 都有因子 2 ，可以用 2 表示出来
所以我们只要每次找一个标记点，如果未访问就以当前点为端点开始框多边形就好了
然后我们考虑两个质因子的情况
假设 (n = 12)
那么 6 边形会比 2、3 边形优么？
显然不会，证毕
处理方法
所以我们的问题就是怎么用这两个正多边形去框住所有的标记点
标算是二分图求最大独立集，但其实并不用那么麻烦
我们令 (p1 ,p2) 为 n 的两个质因子
那么我们可以发现把 n 个点分成 (n/(p1·p2)) 份后（也就是隔 (p1·p2) 个点选一个点，总共选 (n/(p1·p2)) 次），这几份点无论如何也不会互相影响，然后我们对于这几份点分别处理就好了
然后我们考虑处理的方式就是对于一份点算出用 正 (p1) 边形 框的和用 正 (p2) 边形 框所会框住的点数，然后贪心取小的就行了
正确性
我们发现在长度为 (p1· p2) 的一份点以内一旦选择了一种正多边形去框点，另一种正多边形就会受到影响（即无法放置任何一个另一种正多边形）
那样我们就可以分别计算两个正多边形需要框的最少点数了
处理一种正多边形框点的答案
考虑从未访问的标记点暴力去跑，每次跳正多边形边数个点，然后沿路标记已访问，并累加答案
这样做的复杂度是 (n/p * p =n) 的，所以复杂度就有了保证
代码实现
//by Judge
#include<queue>
#include<cstdio>
#include<cstring>
#include<iostream>
#define fp(i,a,b) for(int i=(a),I=(b)+1;i<I;++i)
#define fd(i,a,b) for(int i=(a),I=(b)-1;i>I;--i)
using namespace std;
const int M=2e4+3;
#ifndef Judge
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
#endif
char buf[1<<21],*p1=buf,*p2=buf;
inline int Min(int a,int b){return a<b?a:b;}
inline int read(){ int x=0,f=1; char c=getchar();
for(;!isdigit(c);c=getchar()) if(c=='-') f=-1;
for(;isdigit(c);c=getchar()) x=x*10+c-'0'; return x*f;
} int n,m,tmp,ans,num,p[5],vis[M],a[M]; vector<int> vec[M];
inline void solv1(){ int now; //可以判一个质因子的情况
fp(i,1,m) if(!vis[a[i]])
fp(j,1,p[1])
now=a[i]+(n/p[1])*j,
now=now%n?now%n:n,
vis[now]|=1,++ans;
if(ans==n) puts("-1");
else printf("%d
",ans-m);
}
inline void solv2(){ //两个质因子的情况
int p1=p[1],p2=p[2],now=n/p1/p2;
fp(i,1,m) vec[a[i]%now].push_back(a[i]);
fp(j,0,now-1){ int res1=0,res2=0;
fp(i,0,vec[j].size()-1)
if(!vis[vec[j][i]]) fp(k,1,p1){
now=vec[j][i]+(n/p1)*k,
now=now%n?now%n:n,
vis[now]|=1,++res1;
}
fp(i,0,vec[j].size()-1) vis[vec[j][i]]=0;
fp(i,0,vec[j].size()-1)
if(!vis[vec[j][i]]) fp(k,1,p2){
now=vec[j][i]+(n/p2)*k,
now=now%n?now%n:n,
vis[now]|=1,++res2;
}
ans+=Min(res1,res2); //贪心取最小
}
if(ans==n) puts("-1");
else printf("%d
",ans-m);
}
int main(){ tmp=n=read(),m=read();
fp(i,1,m) a[i]=read();
for(int i=2;i*i<=tmp;++i)if(!(tmp%i))
for(p[++num]=i;!(tmp%i);tmp/=i);
if(tmp>1) p[++num]=tmp;
if(!p[2]) return solv1(),0;
else return solv2(),0;
}