求所有不超过1e9的 primitive Pythagorean triple中第2大的数取模$2^k$作为下标，对应a[i]数组的和。

先上WIKI:https://en.wikipedia.org/wiki/Pythagorean_triple

里面有通过欧几里得公式来得到有关毕达哥拉斯式子的一些性质。

最后得到的一个关于互质的m,n变种的式子更加直观，因此枚举m,n，保证其合法。每次枚举n，筛掉和n有共同因子的m，范围是$\sqrt{1e9}$。然后由于要求的是b，而且取模的都是2的幂指，因此可以先预处理所有$b%(2^{17})$的个数，最后再模$(2^k) $即可。

但是用这个方法做这道题还会卡取模的常数，需要把取模换成$\&(2^{17} - 1)$

另一提，半夜两点和偶像在做同这题，人家是1A秒杀，而且代码很短，还是蛮高兴的，并不（。

/** @Date    : 2017-09-17 23:49:14

  * @FileName: HDU 6211 青岛网络1006 欧几里得 数论.cpp

  * @Platform: Windows

  * @Author  : Lweleth (SoungEarlf@gmail.com)

  * @Link    : https://github.com/

  * @Version : $Id$

  */

#include <bits/stdc++.h>

#define LL long long

#define PII pair<int ,int>

#define MP(x, y) make_pair((x),(y))

#define fi first

#define se second

#define PB(x) push_back((x))

#define MMG(x) memset((x), -1,sizeof(x))

#define MMF(x) memset((x),0,sizeof(x))

#define MMI(x) memset((x), INF, sizeof(x))

using namespace std;

const int INF = 0x3f3f3f3f;

const int N = 32000;

const double eps = 1e-8;

int pri[N];

bool vis[N];

int c = 0;

int prime()

{

	MMF(vis);

	for(int i = 2; i < N; i++)

	{

		if(!vis[i]) pri[c++] = i;

		for(int j = 0; j < c && i * pri[j] < N; j++)

		{

			vis[i * pri[j]] = 1;

			if(i % pri[j] == 0) break;

		}

	}

}

LL coe[(1 << 17) + 20];

LL s[(1 << 17) + 20];

LL MA = (1LL<<17);

int main()

{

	int T;

	MMF(coe);

	prime();

	//cout << c << endl;

	for(int i = 1; i * i <= 1000000000; i++)

	{

		MMF(vis);

		int t = i;

		for(int j = 0; j < c && pri[j] * pri[j] <= t; j++)

		{

			if(t % pri[j] == 0)

			{

				while(t % pri[j] == 0)

					t /= pri[j];

				for(int k = pri[j]; k <= N; k+=pri[j])

					if(!vis[k]) vis[k] = 1;

			}

		}

		if(t > 1)

			for(int k = t; k < N; k+=t)

					if(!vis[k]) vis[k] = 1;

		for(int j = i + 1; j * j + i * i <= 1000000000; j++)

		{

			if(!vis[j]/*__gcd(i, j) == 1*/ && !(j&1 && i&1))

			{

				int a = 2 * i * j;

				int b = j * j - i * i;

				coe[max(a, b) & (MA - 1)]++;

				//ans += s[max(a, b) % MA];

			}

		}					//cout << ans << endl;

	}

	scanf("%d", &T);

	while(T--)

	{

		int n;

		scanf("%d", &n);

		LL ans = 0;

		int ma = (1 << n);

		for(int i = 0; i < ma; i++)

			scanf("%lld", s + i);

		for(int i = 0; i < MA; i++)

			ans += (LL)s[i & (ma - 1)] * coe[i];

		printf("%lld\n", ans);

	}

    return 0;

}

/*

5

2

0 0 0 1

2

1 0 0 0

2

1 1 1 1

*/

//https://en.wikipedia.org/wiki/Pythagorean_triple