CF 71C Round Table Knights 暴力

题意:一个圆上有n个点,每个点距离都相同,第i个点颜色颜色为黑色或者白色.

n<=1e5,问圆上的黑点是否能组成某个正多边形?

假如第i个点为起点,到下一个黑点距离为d,若i,i+d,i+2d,i+kd..,i都为黑点 则存在正多边形.

枚举i和d,d必须为n的约数,并且距离为d时,起点有d个,暴力跳一下即可.O(n*D)(应该也可以分段来?本题似乎没有必要.,D为因子个数)

注意对于d个起点 只要for一次序列,记c[num]为第num个起点的结果 c[num]&=a[i] (i-num)%d==0.

#include <bits/stdc++.h>
using namespace std;
const int N=1e5+20,M=505;
int n,a[N];
bool c[N];
vector<int> v;
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
		scanf("%d",&a[i]);
	bool flag=false;
	for(int i=1;i*i<=n;i++)
	{
		if(n%i==0)
		{
			v.push_back(i);
			if(i*i!=n)
				v.push_back(n/i);
		}
	}
	sort(v.begin(),v.end());
	for(int i=0;i<v.size()-1;i++)
	{
		int d=v[i];
		if(n/d<=2)
			continue;
		int num=1;
		memset(c,true,sizeof(c));
		for(int j=1;j<=n;j++)
		{
			c[num]&=a[j];
			num++;
			if(num>d)
				num=1;
		}
		for(int j=1;j<=d;j++)
		{
			if(c[j])
			{
				flag=true;
				break;
			}
		}
	}
	if(flag)
		printf("YES\n");
	else
		printf("NO\n");
	return 0;
}