Description：

求： $$ (\sum_{i=1}^A\sum_{j=1}^B\sum_{k=1}^C\sigma_0(ijk))\mod (10^9+7) $$ $1\leqslant A,B,C\leqslant 10^5$

Solution：

首先有结论： $$ \sigma_0(ijk)=\sum_{d_1|i}\sum_{d_2|j}\sum_{d_3|k}[\gcd(d_1,d_2)=1][\gcd(d_1,d_3)=1][\gcd(d_2,d_3)=1] $$ 所以把上面那个式子按照这个反演得： $$ \begin{align} &\sum_{i=1}^A\sum_{j=1}^B\sum_{k=1}^C\sum_{d_1|i}\sum_{d_2|j}\sum_{d_3|k}\sum_{t_1|d_1,t_1|d_2}\mu(t_1)\sum_{t_2|d_1,t_2|d_3}\mu(t_2)\sum_{t_3|d_2,t_3|d_3}\mu(t_3)\\ =&\sum_{d_1=1}^A\lfloor\frac A {d_1}\rfloor\sum_{d_2=1}^B\lfloor\frac B {d_2}\rfloor\sum_{d_3=1}^C\lfloor\frac C {d_3}\rfloor\sum_{t_1|d_1,t_1|d_2}\mu(t_1)\sum_{t_2|d_1,t_2|d_3}\mu(t_2)\sum_{t_3|d_2,t_3|d_3}\mu(t_3)\\ =&\sum_{t_1=1}^{\min(A,B)}\mu(t_1)\sum_{t_2=1}^{\min(A,C)}\mu(t_2)\sum_{t_3=1}^{\min(B,C)}\mu(t_3)\sum_{t_1|d_1,t_2|d_1}\lfloor\frac A {d_1}\rfloor\sum_{t_1|d_2,t_3|d_2}\lfloor\frac B {d_2}\rfloor\sum_{t_2|d_3,t_3|d_3}\lfloor\frac C {d_3}\rfloor\\ \end{align} $$ 这个时候就需要观察式子的性质，会发现后面那部分并不与整体相关，于是设： $$ f(n,x)=\sum_{n|d}\lfloor\frac x d\rfloor $$ 这时有： $$ =\sum_{t_1=1}^{\min(A,B)}\mu(t_1)\sum_{t_2=1}^{\min(A,C)}\mu(t_2)\sum_{t_3=1}^{\min(B,C)}\mu(t_3)f(\text{lcm}(t_1,t_2),A)f(\text{lcm}(t_1,t_3),B)f(\text{lcm}(t_2,t_3),C) $$ 这个时候我们会发现式子没发再推了，考虑怎么样才能降下来复杂度。

首先 $n>x$ 的 $f(n,x)$ 都是 $0$ ，有一个 $\mu$ 为 $0$ 的也是 $0$ ，如果我们往符合条件的 $t_1,t_2$ 之间连一条边，那么只有三元环会产生贡献（可以有自环，也就是说由三条边组成的环）。那么我们就可以枚举 $\text{lcm}$ ， $\mu(\text{lcm})$ 必须为零，然后枚举因子暴力建边，可以发现这样最后建出的边不会很多，找三元环的话有一个技巧是从度数大的点连向度数小的点，这样由根号分治的复杂度计算可以得到复杂度为 $O(m\sqrt m)$ 。

感觉这题复杂度好玄学啊。用 $vector$ 减少 $\texttt{cache miss}$ 卡常。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<vector>

#include<cctype>

#include<cstring>

using namespace std;

typedef long long ll;

#define R register

int a,b,c;

#define MAXN 100010

bool isprime[MAXN];

int prime[MAXN],tot = 0;

int mu[MAXN];

int fac[MAXN][14];

int mindiv[MAXN];

ll fa[MAXN],fb[MAXN],fc[MAXN];

void init()

{

	for(R int i = 2;i < MAXN;++i)isprime[i] = true;

	mu[1] = 1;mindiv[1] = 1;

	for(R int i = 2;i < MAXN;++i)

	{

		if(isprime[i])

		{

			mu[i] = -1;mindiv[i] = i;

			prime[++tot] = i;

		}

		for(R int j = 1;j <= tot && i * prime[j] < MAXN;++j)

		{

			isprime[i * prime[j]] = false;

			mindiv[i * prime[j]] = prime[j];

			if(i % prime[j] == 0)

			{

				mu[i * prime[j]] = 0;

				break;

			}

			else

			{

				mu[i * prime[j]] = -mu[i];

			}

		}

	}

	for(R int i = 1;i < MAXN;++i)

	{

		R int s = i;

		while(s != 1)

		{

			R int k = mindiv[s];

			fac[i][++fac[i][0]] = mindiv[s];

			while(s % k == 0)s /= k;

		}

	}

	return;

}

struct edges

{

	int u,v,w;

}es[800010];

int edgecnt = 0;

int gcd(int a,int b){return (b == 0 ? a : gcd(b,a % b));}

int lcm(int a,int b){return a / gcd(a,b) * b;}

int deg[MAXN];

vector< pair<int,int> > e[MAXN];

#define MOD 1000000007

void work()

{

	scanf("%d%d%d",&a,&b,&c);

	memset(fa,0,sizeof(fa));

	memset(fb,0,sizeof(fb));

	memset(fc,0,sizeof(fc));

	memset(deg,0,sizeof(deg));

	edgecnt = 0;

	R int v = max(a,max(b,c));

	for(R int i = 1;i <= v;++i)e[i].clear();

	for(R int i = 1;i <= a;++i)for(int d = i;d <= a;d += i)fa[i] = (fa[i] + a / d) % MOD;

	for(R int i = 1;i <= b;++i)for(int d = i;d <= b;d += i)fb[i] = (fb[i] + b / d) % MOD;

	for(R int i = 1;i <= c;++i)for(int d = i;d <= c;d += i)fc[i] = (fc[i] + c / d) % MOD;

	for(R int i = 1;i <= v;++i)

	{

		if(mu[i] == 0)continue;

		for(int j = 0;j <= (1 << fac[i][0]) - 1;++j)

		{

			R int x = 1;

			for(R int s = 1;s <= fac[i][0];++s)if(j & (1 << (s - 1)))x *= fac[i][s];

			for(R int k = j;k >= 0;k = (k - 1) & j)

			{

				R int y = 1;

				for(R int s = 1;s <= fac[i][0];++s)if(k & (1 << (s - 1)))y *= fac[i][s];

				y = i / x * y;

				if(x < y)es[++edgecnt] = (edges){x,y,i};

				if(k == 0)break;

			}

		}

	}

	for(R int i = 1;i <= edgecnt;++i)++deg[es[i].u],++deg[es[i].v];

	for(R int i = edgecnt;i >= 1;--i)

	{

		if(deg[es[i].u] < deg[es[i].v])swap(es[i].u,es[i].v);

		e[es[i].u].push_back(make_pair(es[i].v,es[i].w));

	}

	R ll ans = 0;

	for(R int k = 1;k <= v;++k)

	{

		if(mu[k] == 0)continue;

		for(R vector< pair<int,int> >::iterator it1 = e[k].begin();it1 != e[k].end();++it1)

		{

			for(R vector< pair<int,int> >::iterator it2 = e[it1 -> first].begin();it2 != e[it1 -> first].end();++it2)

			{

				if(lcm(it2 -> first,k) > v)continue;

				R int v3 = lcm(it2 -> first,k),v1 = it1 -> second,v2 = it2 -> second;

				R int val = mu[it2 -> first] * mu[it1 -> first] * mu[k];

				R ll sum = 0;

				sum = sum + fa[v1] * fb[v2] % MOD * fc[v3] % MOD;

				sum = sum + fa[v1] * fb[v3] % MOD * fc[v2] % MOD;

				sum = sum + fa[v2] * fb[v1] % MOD * fc[v3] % MOD;

				sum = sum + fa[v2] * fb[v3] % MOD * fc[v1] % MOD;

				sum = sum + fa[v3] * fb[v1] % MOD * fc[v2] % MOD;

				sum = sum + fa[v3] * fb[v2] % MOD * fc[v1] % MOD;

				ans += sum * val;

			}

		}

	}

	for(R int i = 1;i <= edgecnt;++i)

	{

		R ll sum,v1,v2;

		sum = 0;

		v1 = es[i].w,v2 = es[i].v;

		sum += fa[v1] * fb[v1] % MOD * fc[v2] % MOD;

		sum += fa[v1] * fb[v2] % MOD * fc[v1] % MOD;

		sum += fa[v2] * fb[v1] % MOD * fc[v1] % MOD;

		ans += sum * mu[es[i].u];

		sum = 0;

		v1 = es[i].w,v2 = es[i].u;

		sum += fa[v1] * fb[v1] % MOD * fc[v2] % MOD;

		sum += fa[v1] * fb[v2] % MOD * fc[v1] % MOD;

		sum += fa[v2] * fb[v1] % MOD * fc[v1] % MOD;

		ans += sum * mu[es[i].v];

	}

	for(R int i = 1;i <= v;++i)

	{

		ans += fa[i] * fb[i] % MOD * fc[i] % MOD * mu[i] % MOD;

	}

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

	return;

}

int main()

{

	init();

	int testcases;

	scanf("%d",&testcases);

	while(testcases--)work();

	return 0;

}