Circle of Numbers
Contest: MemSQL Start[c]UP 3.0 - Round 1
Difficulty rating: 3000
Tags: math

n evenly spaced points have been marked around the edge of a circle. There is a number written at each point. You choose a positive real number k. Then you may repeatedly select a set of 2 or more points which are evenly spaced, and either increase all numbers at points in the set by k or decrease all numbers at points in the set by k. You would like to eventually end up with all numbers equal to 0. Is it possible?

A set of 2 points is considered evenly spaced if they are diametrically opposed, and a set of 3 or more points is considered evenly spaced if they form a regular polygon.

Input format:
The first line of input contains an integer n (3 ≤ n ≤ 100000), the number of points along the circle.

The following line contains a string s with exactly n digits, indicating the numbers initially present at each of the points, in clockwise order.

Output format:
Print "YES" (without quotes) if there is some sequence of operations that results in all numbers being 0, otherwise "NO" (without quotes).

You can print each letter in any case (upper or lower).

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

Note:
If we label the points from 1 to n, then for the first test case we can set k = 1. Then we increase the numbers at points 7 and 22 by 1, then decrease the numbers at points 7, 17, and 27 by 1, then decrease the numbers at points 4, 10, 16, 22, and 28 by 1.

Example input:
30
000100000100000110000000001100

Example output:
YES

Example input:
6
314159

Example output:
NO

Editorial:
Construct polynomial P(x) = si·xi. For p|n denote Qp(x) = 1 + xn / p + x2n / p + ... + x(p - 1)n / p = (xn - 1) / (xn / p - 1). Our task is to determine if P(x) can be written as a linear combination of Qi(x) polynomials. Bézout's Identity tells us that a solution exists if the greatest common divisor of the Qi(x) polynomials also divides P(x), and the familiar Extended Euclidean Algorithm could be used to construct a solution if needed.
Let's compute the GCD of the Qi(x) polynomials, and call it G(x). Let ω = e2π i / n. Then $$Q_p(x) = \prod_{0 \leq i < n, p \nmid i} (x - \omega^i)$$. Therefore $$G(x) = \prod_{0 \leq i < n, gcd(i,n)=1} (x - \omega^i)$$. This is equal to the Cyclotomic Polynomial Φn(x).
Directly testing P(x) for divisibility by G(x) is quite expensive. Instead, denote F as the set of prime factors of n and let $$R(x) = \prod_{i \in F} (x^{n/i} - 1)$$. Note that for each i, $$( x - \omega ^ { i } ) | R ( x ) \Longleftrightarrow gcd(i,n) \neq 1$$. It follows that $$G(x) \mid P(x) \iff (x^n - 1) \mid P(x) \cdot R(x)$$. The latter can be easily computed.
Alternate solution: Note that a necessary condition is that if we place weights on each point equal in magnitude to the number, then the center of gravity must be at exactly the center of the circle. Attempting to compute the center of gravity numerically isn't guaranteed to work because it could be extremely close to the center (we were able to construct test cases where it was within 10 - 500 of the center). However, if we choose some integer m relatively prime to n, and for each point i move its number to point m·i, then the answer does not change, but the center of gravity might. We can check the center of gravity numerically for several random m, and if it's ever not within the margin of numerical error then the answer must be no. In theory this could still fail but in practice it was always easy to find a value of m where the center of gravity is quite far from the actual center. Another way to probabilistically test if the center of gravity is at the center is to choose a random prime p such that n|p - 1, and a random r such that $$r^n \equiv 1 \mod p$$. Then it must be the case that $$P(r) \equiv 0 \mod p$$.