题意：
求$x ^ 2 + 3 y ^ 2 = n ^ 2$上整点的个数。
题解：
和bzoj 1041: [HAOI2008]圆上的整点很像，但数据范围大很多。事实上因为约数个数挺少的，所以还是可以直接做。
代码：
#include <bits/stdc++.h>
#define pa pair<long long, int>
using namespace std;
int T, ans = 0;
long long n;
bool not_prime[1000010];
vector<int> prime;
vector<pa> s;
long long gcd(long long x, long long y) { return y == 0 ? x : gcd(y, x % y); }
void pre(int n = 1000000)
{
for (int i = 2; i <= n; i++)
{
if (!not_prime[i])
{
prime.push_back(i);
}
for (int j = 0; j < prime.size() && 1LL * prime[j] * i <= n; j++)
{
not_prime[prime[j] * i] = 1;
if (i % prime[j] == 0) break;
}
}
}
void get_s(long long x)
{
s.clear();
for (int i = 0; i < prime.size() && 1LL * prime[i] * prime[i] <= x; i++)
if (x % prime[i] == 0)
{
s.push_back(make_pair(prime[i], 0));
while (x % prime[i] == 0) x /= prime[i], s.back().second++;
}
if (x > 1) s.push_back(make_pair(x, 1));
}
void dfs(int x, long long now)
{
if (x == s.size())
{
// printf("%lld\n", now);
long long hh = now;
for (int j = 1; 6LL * j * j < hh; j++)
{
int oo = lround(sqrt(hh - 3LL * j * j));
if (1LL * oo * oo == hh - 3LL * j * j && gcd(1LL * oo * oo, 3LL * j * j) == 1) ans++;
}
for (int j = 1; 2LL * j * j < hh; j++)
if ((hh - 1LL * j * j) % 3 == 0)
{
int oo = lround(sqrt((hh - 1LL * j * j) / 3));
if (3LL * oo * oo == hh - 1LL * j * j && gcd(3LL * oo * oo, 1LL * j * j) == 1) ans++;
}
return;
}
dfs(x + 1, now);
for (int i = 0; i < s[x].second; i++)
{
now *= s[x].first;
dfs(x + 1, now);
}
}
int main()
{
// freopen("4544.in", "r", stdin);
// freopen("4544.out", "w", stdout);
pre();
scanf("%d", &T);
while (T--)
{
ans = 0;
scanf("%lld", &n);
n <<= 1;
get_s(n);
dfs(0, 1);
printf("%d\n", ans * 4 + 2);
}
}