Problem Statement

一個(gè)二進(jìn)制序列由下面的偽代碼生成：

string A = "0"
            While (A的長(zhǎng)度小于等于n)
            創(chuàng)建一個(gè)和A一樣長(zhǎng)度的字符串B
            For i=0,1,...length(A)-1
            If (i 是完全平方數(shù))
            B[i] = 1-A[i]
            Else
            B[i] = A[i]
            令A(yù) = A + B (即將B拼接在A后面)
            End While
            Return A

請(qǐng)注意，在上面的偽代碼中，A[i]和B[i]分別表示字符串A和B中下標(biāo)為i的字符（下標(biāo)編號(hào)從0開(kāi)始）。對(duì)“完全平方數(shù)”的定義是，對(duì)于整數(shù)i，存在整數(shù)j，使得i= j *j，則稱i為完全平方數(shù)。

下面具體說(shuō)明序列生成的過(guò)程：如果n=7，則在每一輪迭代中，A的取值依次為：0, 01, 0110, 01101010，所以最終產(chǎn)生的二進(jìn)制序列就是0,1,1,0,1,0,1,0

請(qǐng)返回上述序列中下標(biāo)為n的數(shù)字（該序列的下標(biāo)從0開(kāi)始）(0=<n<=2,000,000,000)

Definition