C++11(clang++ 3.9) 解法, 执行用时: 334ms, 内存消耗: 1516K, 提交时间: 2020-03-14 14:48:13

#include<bits/stdc++.h>
#define rep(i,x,y) for(int i=x,_=y;i<_;++i)
#define down(i,x,y) for(int i=x-1,_=y;i>=_;--i)
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define bin(x) 1<<x
#define SZ(x) int(x.size())
#define LX_JUDGE
using namespace std;
typedef pair<int,int> pii;
typedef vector<int> Vi;
typedef long long ll;
template<typename T> inline bool upmax(T &x,T &y)
{
	return x<y?(x=y,1):0;
}
template<typename T> inline bool upmin(T &x,T &y)
{
	return x>y?(x=y,1):0;
}
namespace MATH_CAL
{
	const int mod=1e9+7;
	inline int add(int a,int b)
	{
		return a+b>=mod?a+b-mod:a+b;
	}
	inline int sub(int a,int b)
	{
		return a-b<0?a-b+mod:a-b;
	}
	inline int mul(int a,int b)
	{
		return (ll)a*b%mod;
	}
	inline void Add(int &a,int b)
	{
		(a+=b)>=mod?a-=mod:0; 
	}
	inline void Sub(int &a,int b)
	{
		(a-=b)<0?a+=mod:0;
	}
	inline int qpow(int x,int n)
	{
		int r=1;
		for(;n;n/=2,x=mul(x,x))
		if(n&1)
		r=mul(r,x);
		return r; 
	}
	inline int mod_inv(int x)
	{
		return qpow(x,mod-2);
	}
} using namespace MATH_CAL;
const int inf=0x3f3f3f3f;
const int MAX_N=1e5+10;
int prime[MAX_N],pcnt;
bool vis[MAX_N];
pii met[MAX_N];
void sieve(int n)
{
	rep(i,2,n)
	{
		if(!vis[i])
		{
			prime[pcnt++]=i;
		}
		rep(j,0,pcnt)
		{
			int to=prime[j]*i;
			if(to>=n) break;
			vis[to]=1;
			if(i%prime[j]==0) break;
		}
	}
	for(int a=0;a*a<n;++a)
	for(int b=0;b*b+a*a<n;++b)
	{
		met[a*a+b*b]=mp(a,b);
	}
}
vector<pii> divs;
int N,M,S;
int U,V;
int ans;
void divide(int step,int k,int now)
{
	if(step==divs.size())
	{
		if(U==0)
		{
			int tmp=0;
			if(N>=k&&M>=now)
			{
				Add(tmp,mul(N-k+1,M-now+1));
			}
			if(N>=now&&M>=k)
			{
				Add(tmp,mul(N-now+1,M-k+1));
			}
			Add(ans,mul(tmp,2));
			return;
		}
		else
		{
			int tmp=0;
			int L=U*k+V*now,H=max(V*k,U*now);
			if(N>=L&&M>=H)
			{
				Add(tmp,mul(N-L+1,M-H+1));
			}
			if(N>=H&&M>=L)
			{
				Add(tmp,mul(N-H+1,M-L+1));
			}
			if(U!=V)
			{
				int L=U*now+V*k,H=max(V*now,U*k);
				if(N>=L&&M>=H)
				{
					Add(tmp,mul(N-L+1,M-H+1));
				}
				if(N>=H&&M>=L)
				{
					Add(tmp,mul(N-H+1,M-L+1));
				}
			}
			Add(ans,mul(tmp,2));
		}
		return;
	}
	int p=divs[step].fi;
	while(1)
	{
		divide(step+1,k,now);
		if(k%p!=0) break;
		k/=p,now*=p;
	}
}
inline void Count(int u,int v)
{
	int k=S/(u*u+v*v);
	U=u,V=v;
	divide(0,k,1);
}
inline void Find(int &x,int &y,int p)
{
	if(p<MAX_N)
	{
		x=met[p].fi;
		y=met[p].se;
		return;
	}
	else
	{
		for(int a=1;a*a<=p;++a)
		{
			int u=p-a*a,v=floor(sqrt(u)+0.5);
			while(v*v>u) v--;
			while((v+1)*(v+1)<=u) v++;
			if(v*v==u)
			{
				x=a,y=v;
				return;
			}
		}
	}
	assert(0);
}
inline void mul(int &a,int &b,int u,int v)
{
	int x=a*u-b*v;
	int y=b*u+a*v;
	a=x;
	b=y;
}
set<pii> G;
void dfs(int step,int u,int v)
{
	if(step==divs.size())
	{
		(u<0)&&(u=-u);
		(v<0)&&(v=-v);
		if(u>v) swap(u,v);
		if(G.count({u,v})) return;
		G.insert({u,v});
		Count(u,v);
		return;
	}
	int p=divs[step].fi,c=divs[step].se;
	int x,y;
	if(p%4==2)
	{
		x=u;
		y=v;
		dfs(step+1,x,y);
		x=u-v;
		y=u+v;
		dfs(step+1,x,y);
	}
	if(p%4==3)
	{
		x=u,y=v;
		dfs(step+1,u,v);
	}
	if(p%4==1)
	{
		int a,b;
		Find(a,b,p);
		int x=u,y=v;
		for(int i=0;i<=c;++i)
		{
			dfs(step+1,x,y);
			mul(x,y,a,b);
		}
		x=u,y=v;
		mul(x,y,a,-b);
		for(int i=1;i<=c;++i)
		{
			dfs(step+1,x,y);
			mul(x,y,a,-b);
		}
	 } 
}
int solve(int n,int m,int s)
{
	G.clear();
	divs.clear();
	ans=0;
	N=n;
	M=m;
	S=s;
	int tmp=s;
	for(int i=0;prime[i]<=tmp&&i<pcnt;++i)
	{
		if(tmp%prime[i]==0)
		{
			int p=prime[i],c=0;
			while(tmp%p==0) tmp/=p,c++;
			divs.pb(mp(p,c));
		}
	}
	if(tmp>1) divs.pb(mp(tmp,1));
	reverse(divs.begin(),divs.end());
	dfs(0,1,0);
	return ans;
}
int main()
{
	sieve(MAX_N);
	int T;
	scanf("%d",&T);
	while(T--)
	{
		int n,m,s;
		scanf("%d%d%d",&n,&m,&s);
		printf("%d\n",solve(n,m,s));
	}
	return 0;
}