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


-----Input-----

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

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


-----Example-----
Input
4
1010

Output
3



-----Note-----

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

Source: codeforces | Difficulty: HARD
Tags: Number theory

Complete search


Solutions:
from math import gcd

def canHash(n, ln):
	if n == '0' * ln:
		return ln
	ans = 0
	yes = []
	for i in range(1, ln):
		if ln % i == 0:
			token = 1
			for k in range(i):
				a = sum([int(b) for b in n[k::i]])
				if a % 2 != 0:
					token = 0
			if token == 1:
				yes.append(i)
				ans += 1
		elif gcd(ln, i) in yes:
			ans += 1
	return ans

def __starting_point():
	ln = int(input())
	print(canHash(input(), ln))
__starting_point()


import math
num = int(input())
x = tuple(map(int, list(input())))
integer = 0
dic = dict()
for i in range(1, num + 1):
	a = math.gcd(i, num)
	if a in dic:
		integer += dic[a]
	else:
		lijst = [0] * a
		for j in range(num):
			b = j % a
			lijst[b] += x[j]
		for k in range(a):
			if lijst[k] % 2 != 0:
				dic[a] = 0
				break
		else:
			integer += 1
			dic[a] = 1
print(integer)


import sys
import math
n = int(sys.stdin.readline().strip())
s = sys.stdin.readline().strip()
a = [1] * n
for c in s:
	if c != '0':
		a[0] = 0
for k in range(1, n):
	if n % k == 0:
		t = [0] * k
		for (i, c) in enumerate(s):
			if c != '0':
				t[i % k] += 1
		if sum([_ % 2 for _ in t]) != 0:
			a[k] = 0
	else:
		a[k] = a[math.gcd(n, k)]
sys.stdout.write('{0}\n'.format(sum(a)))