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 < 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 $ .