P3794 Check-in Problem IV

It seems the other problems in this monthly contest have long backgrounds, so this one will skip the background. 

Given a sequence of length $n$, $[a_1, a_2, \ldots, a_n]$, where each number is a positive integer. You need to find how many pairs $(i, j)$ satisfy $1 \le i \le j \le n$ and $\gcd(a_i, a_{i+1}, \ldots, a_j) \operatorname{xor} (a_i \operatorname{or} a_{i+1} \operatorname{or} \cdots \operatorname{or} a_j) = k$, where $\operatorname{xor}$ denotes bitwise XOR and $\operatorname{or}$ denotes bitwise OR.

The first line contains two integers $n$ and $k$. The second line contains $n$ integers $a_1, a_2, \cdots, a_n$.

Output the number of valid pairs $(i, j)$.

- For $30\%$ of the testdata, $n \le 500$. - For $60\%$ of the testdata, $n \le 100000$. - For $100\%$ of the testdata, $1 \le n, a_i \le 500000$. Translated by ChatGPT 5