参考：
https://matiji.net/exam/brushquestion/36/3846/4C6668FEB8CFD6520DE73B365B31D1A4
bb

问题引入

在一个圆上均匀分布（等距）着n个点，每个点都有一个标记，不是0就是1。

请问能否由若干个标记为1的点依次连接形成正多边形?

格式


输入格式：
第一行包含一个整数 n (3≤n≤100000)(3 \leq n \leq 100000) ；
第二行 n 个标记，以空格分割，含义如题。
输出格式:
若能形成正多边形则输出“YES”，否则输出“NO”(答案无引号)。


样例


输入:
6
1 0 1 1 1 0
输出：
YES


问题分析

其实一开始是没有思路的，去问了bb大佬后。明白了以下规律：

  1. 首先，如果构不成正s边形，就一定构不成st边形
  2. 只要判断n的每个素因子边数的正多边形就可以了
  3. 考虑s边的正多边形，就先暴力的以1, … ,s为起点看看

所以照着这些，我尝试着写出了自己的代码。

题解代码

首先是写一个求 n 的素因子的函数。

数据的输入就不要多说了。将点集存在 point 列表里面，然后计算其中1的个数，以便确定正多边形的最大边数。

最后就是按照上述来写代码。代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
from math import *

def getprimes(n):

    primes = []

    if n % 2 == 0:
        primes.append(2)
    while n % 2 == 0:
        n /= 2

    for i in range(3,int(sqrt(n)+1),2):
        if n % i == 0:
            primes.append(int(i))
        while n % i == 0:
            n /= i
    
    if n > 2:
        primes.append(int(n))

    return primes


n = int(input())
point = list(map(int,input().split()))
sum_one = sum(point)
flag = 0
flag2 = 0


primes = getprimes(n)   #存储n的素因子

#找正s边形，s为n的素因子
for i in primes:
    if i == 2:
        continue
    if i > sum_one:
        break
    for j in range(n):
        j2 = j
        t = n / i   #正多边形顶点坐标的间隔
        flag == 0   #符合正多边形的顶点的数量
        if point[j2%n] == 1:
            flag += 1   
            while flag < i:
                j2 = int((j2+t) % n)
                if point[j2] == 1:
                    flag += 1
                else:
                    break
            if flag == i:
                print('YES')
                flag2 = 1
                break
    
    if flag2:
        break

if flag2 == 0:
    print('NO')


OvO