CF1184A2.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 \lt 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.

学习了多项式哈希之后，Heidi 决定学习移位-异或（shift-xor）哈希。特别是，她遇到了这个有趣的问题：

给定一个长度为 $n$ 的比特串 $y \in \{0,1\}^n$，求满足如下条件的不同 $k$（其中 $0 \leq k < n$）的个数：存在某个 $x \in \{0,1\}^n$，使得 y = x \oplus \mbox{shift}^k(x)。

其中，$\oplus$ 表示按位异或（XOR）运算，\mbox{shift}^k 表示将一个比特串循环右移 $k$ 位的操作。例如，$001 \oplus 111 = 110$，且 \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$.

第一行包含一个整数 $n$（$1 \leq n \leq 2 \cdot 10^5$），表示位串 $y$ 的长度。

第二行包含位串 $y$。

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

输出一个整数：满足条件的 $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$.

在第一个例子中：

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

不存在满足 $x \oplus x = 1010$ 的 $x$，因此答案为 $3$。