A12737. Heidi Learns Hashing (Medium)

After learning about polynomial hashing, Heidi decided to learn about shift-xor hashing. In particular, she came across this interesting problem.

Given a bitstring $y \in \{0,1\}^n$ find out the number of different $k$ ( $0 \leq k < n$ ) such that there exists $x \in \{0,1\}^n$ for which $y = x \oplus \mbox{shift}^k(x).$

In the above, $\oplus$ is the xor operation and $\mbox{shift}^k$ is the operation of shifting a bitstring cyclically to the right $k$ times. For example, $001 \oplus 111 = 110$ and $\mbox{shift}^3(00010010111000) = 00000010010111$ .

The first line contains an integer $n$ ( $1 \leq n \leq 2 \cdot 10^5$ ), the length of the bitstring $y$ .

The second line contains the bitstring $y$ .

Output a single integer: the number of suitable values of $k$ .

In the first example:

- $1100\oplus \mbox{shift}^1(1100) = 1010$
- $1000\oplus \mbox{shift}^2(1000) = 1010$
- $0110\oplus \mbox{shift}^3(0110) = 1010$

There is no $x$ such that $x \oplus x = 1010$ , hence the answer is $3$ .