题解
枚举素勾股数。
这道题由于数据很大，所以肯定要一开始就枚举好。
枚举的时候要注意，使用gcd会超时，所以改为使用枚举素因子判断互质。
由于$\sqrt{1000000000} \approx 31622$，而$2\times 3\times 5\times 7\times 11\times 13\times 17 > 31622$，所以素因子最多不会超过6个。
这样的话效率就比较好了。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
using namespace std;
typedef long long ll;
int read(){
int f = 1, x = 0;
char c = getchar();
while(c < '0' || c > '9'){if(c == '-') f = -f; c = getchar(); }
while(c >= '0' && c <= '9')x = x * 10 + c - '0', c = getchar();
return f * x;
}
int cnt[200005] = {0}, tot = 0;
int p[10], a[200005];
void init(){
for(int v = 2; v <= 31622; ++v){
int pcnt = 0, t = v;
for(int i = 2; i * i <= v; ++i){
if(t % i == 0){
t /= i;
while(t % i == 0)
t /= i;
p[++pcnt] = i;
if(t == 1)
break ;
}
}
if(t != 1)
p[++pcnt] = t;
for(int u = (v % 2 == 0) ? 1 : 2; u < v; u += 2){
int cc = u * u + v * v, flag = 1;
if(cc > 1000000000)
break;
for(int i = 1; i <= pcnt; ++i)
if(u % p[i] == 0){
flag = 0;
break ;
}
if(!flag) continue ;
int aa = v * v - u * u, bb = 2 * u * v;
if(aa > bb)
cnt[(aa & 131071)]++;
else
cnt[(bb & 131071)]++;
}
}
}
void solve(){
int k = read(), t;
k = (1 << k), t = k - 1;
for(int i = 0; i < k; ++i)
a[i] = read();
ll ans = 0;
for(int i = 0; i < 131072; ++i)
ans += 1ll * cnt[i] * a[(i & t)];
printf("%lld\n", ans);
}
int main(){
int T = read();
init();
while(T--)
solve();
return 0;
}