Pythagoras

Given a list of integers $a_0,a_1,a_2,\cdots,a_{2^k-1}$. Pythagoras triples over $10^9$ are all solutions of $x^2+y^2=z^2$ where $x,y$ and $z$ are constrained to be positive integers less than or equal to $10^9$. You are to compute the sum of $a_{y~mod~2^k}$ of triples $(x,y,z)$ such that $x<y<z$ and they are relatively prime, i.e., have no common divisor larger than $1$.

The first line is an integer $T~(1\le T\le 3)$ indicating the total number of cases.
For each test case the first line is the integer $k~(1\le k\le 17)$.
The second line contains $2^k$ integers corresponding to $a_0$ to $a_{2^k-1}$, where each $a_i$ satisfies $1\le a_i\le 255$.

For each case output the sum of $a_{y~mod~2^k}$ in a line.

3
2
0 0 0 1
2
1 0 0 0
2
1 1 1 1

39788763
79577506
159154994

2017 ACM/ICPC Asia Regional Qingdao Online