C. Round Table Knights

Codeforces

IDCF71C

Time2000ms

Memory256MB

Difficulty—

dpmathnumber theory

English · Original

Chinese · Translation

Formal · Original

There are _n_ knights sitting at the Round Table at an equal distance from each other. Each of them is either in a good or in a bad mood. Merlin, the wizard predicted to King Arthur that the next month will turn out to be particularly fortunate if the _regular_ polygon can be found. On all vertices of the polygon knights in a good mood should be located. Otherwise, the next month will bring misfortunes. A convex polygon is regular if all its sides have same length and all his angles are equal. In this problem we consider only regular polygons with at least 3 vertices, i. e. only nondegenerated. On a picture below some examples of such polygons are present. Green points mean knights in a good mood. Red points mean ones in a bad mood. <center>![image](https://espresso.codeforces.com/74f876ccab06b18381319757d775aafd5756bf26.png)</center>King Arthur knows the knights' moods. Help him find out if the next month will be fortunate or not. ## Input The first line contains number _n_, which is the number of knights at the round table (3 ≤ _n_ ≤ 105). The second line contains space-separated moods of all the _n_ knights in the order of passing them around the table. "1" means that the knight is in a good mood an "0" means that he is in a bad mood. ## Output Print "_YES_" without the quotes if the following month will turn out to be lucky. Otherwise, print "_NO_". [samples]

有 #cf_span[n] 位骑士围坐在圆桌旁，彼此等距分布。每位骑士要么心情良好，要么心情不佳。魔法师梅林预示亚瑟王：如果能找到一个 _正多边形_，则下个月将特别幸运——该正多边形的所有顶点上都必须是心情良好的骑士；否则，下个月将带来不幸。一个凸多边形是正多边形，当且仅当它的所有边长度相等且所有内角相等。本题中我们仅考虑至少有 3 个顶点的正多边形，即非退化的。下图展示了此类多边形的一些示例。绿色点表示心情良好的骑士，红色点表示心情不佳的骑士。亚瑟王知道每位骑士的心情。请帮他判断下个月是否会幸运。第一行包含数字 #cf_span[n]，表示圆桌旁骑士的数量（#cf_span[3 ≤ n ≤ 105]）。第二行按顺时针顺序给出所有 #cf_span[n] 位骑士的心情，用空格分隔。"1" 表示该骑士心情良好，"0" 表示心情不佳。如果下个月会幸运，请输出 "_YES_"（不含引号）；否则输出 "_NO_"。 ## Input 第一行包含数字 #cf_span[n]，表示圆桌旁骑士的数量（#cf_span[3 ≤ n ≤ 105]）。第二行按顺时针顺序给出所有 #cf_span[n] 位骑士的心情，用空格分隔。"1" 表示该骑士心情良好，"0" 表示心情不佳。 ## Output 如果下个月会幸运，请输出 "_YES_"（不含引号）；否则输出 "_NO_"。 [samples]

**Definitions** Let $ n \in \mathbb{Z} $ with $ 3 \leq n \leq 10^5 $ be the number of knights seated equally spaced on a circle. Let $ A = (a_0, a_1, \dots, a_{n-1}) \in \{0,1\}^n $ be the sequence of moods, where $ a_i = 1 $ if knight $ i $ is in a good mood, and $ a_i = 0 $ otherwise. **Constraints** The knights are positioned at the $ n $-th roots of unity on the unit circle, i.e., at angles $ \frac{2\pi i}{n} $ for $ i = 0, 1, \dots, n-1 $. **Objective** Determine whether there exists an integer $ d $, with $ 2 \leq d < n $ and $ d \mid n $, such that the regular $ \frac{n}{d} $-gon formed by selecting every $ d $-th knight (starting from some index) has all its vertices at positions where $ a_i = 1 $. Equivalently, determine if there exists a divisor $ k \geq 3 $ of $ n $ and an offset $ r \in \{0, 1, \dots, d-1\} $, where $ d = \frac{n}{k} $, such that: $$ \forall j \in \{0, 1, \dots, k-1\}, \quad a_{(r + j \cdot d) \bmod n} = 1 $$ **Output** Print "YES" if such a regular polygon exists; otherwise, print "NO".

Samples

Input #1

3
1 1 1

Output #1

YES

Input #2

6
1 0 1 1 1 0

Output #2

YES

Input #3

6
1 0 0 1 0 1

Output #3

NO

API Response (JSON)

{
  "problem": {
    "name": "C. Round Table Knights",
    "description": {
      "content": "There are _n_ knights sitting at the Round Table at an equal distance from each other. Each of them is either in a good or in a bad mood. Merlin, the wizard predicted to King Arthur that the next mon",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF71C"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "There are _n_ knights sitting at the Round Table at an equal distance from each other. Each of them is either in a good or in a bad mood.\n\nMerlin, the wizard predicted to King Arthur that the next mon...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "有 #cf_span[n] 位骑士围坐在圆桌旁，彼此等距分布。每位骑士要么心情良好，要么心情不佳。\n\n魔法师梅林预示亚瑟王：如果能找到一个 _正多边形_，则下个月将特别幸运——该正多边形的所有顶点上都必须是心情良好的骑士；否则，下个月将带来不幸。\n\n一个凸多边形是正多边形，当且仅当它的所有边长度相等且所有内角相等。本题中我们仅考虑至少有 3 个顶点的正多边形，即非退化的。\n\n下图展示了此类多边形的...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ n \\in \\mathbb{Z} $ with $ 3 \\leq n \\leq 10^5 $ be the number of knights seated equally spaced on a circle.  \nLet $ A = (a_0, a_1, \\dots, a_{n-1}) \\in \\{0,1\\}^n $ be the sequenc...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments