时光匆匆，转眼间又是一年寒暑……
这是小 Q 同学第二次参加省队选拔赛。
今年，小 Q 痛定思痛，不再冒险偷取试题，而是通过练习旧 试题提升个人实力。可是旧试题太多了，小 Q 没日没夜地做题，却看不到前方的光明在哪里。
一天，因做题过度而疲惫入睡的小 Q 梦到自己在考场上遇到了一道好像做过的题目，却怎么也想不 起曾经自己是怎么解决它的，直到醒来还心有余悸。
小 Q 眉头一皱，感觉事情不妙，于是他找到了你，希望你能教他解决这道题目。小 Q 依稀记得题目 要计算如下表达式的值
$({\sum_{i=1}^{A}}{\sum_{j=1}^{B}}{\sum_{k=1}^{C}}d(ijk))mod(10^9+7)$
其中 d(ijk) 表示 ijk 的约数个数。
Input
第一行包含一个正整数 T，表示有 T 组测试数据。 接下来 T 行，每行描述一组测试数据，包含三个整数 A, B 和 C，含义见题目描述。
Output
对于每组测试数据，输出一行，包含一个整数，表示所求表达式的值。
解题思路：
极限卡常题，具体卡常的方法主要是使用vector代替链式前向星，如果还过不去，还是看看dalao们的博客吧。
这里主要讲算法。
首先是喜闻乐见的莫比乌斯反演，三个$\sum$有点中暑，慢慢推吧其实都差不多。
不妨设$A\leq B\leq C$,则:
$Ans={\sum_{i=1}^{A}}{\sum_{j=1}^{B}}{\sum_{k=1}^{C}}d(ijk)$
$={\sum_{i=1}^{A}}{\sum_{x|i}}{\sum_{j=1}^{B}}{\sum_{y|j}}{\sum_{k=1}^{C}}{\sum_{z|k}}{\varepsilon(gcd(x,y))}{\varepsilon(gcd(y,z))}{\varepsilon(gcd(x,z))}$
$={\sum_{x=1}^{A}}{\sum_{x|i}^{A}}{\sum_{y=1}^{B}}{\sum_{y|j}^{B}}{\sum_{z=1}^{C}}{\sum_{z|k}^{C}}{\varepsilon(gcd(x,y))}{\varepsilon(gcd(y,z))}{\varepsilon(gcd(x,z))}$
$={\sum_{x=1}^{A}}{\sum_{y=1}^{B}}{\sum_{z=1}^{C}}{\left\lfloor{\frac{A}{x}}\right\rfloor}{\left\lfloor{\frac{B}{y}}\right\rfloor}{\left\lfloor{\frac{C}{z}}\right\rfloor}{\varepsilon(gcd(x,y))}{\varepsilon(gcd(y,z))}{\varepsilon(gcd(x,z))}$
$={\sum_{x=1}^{A}}{\sum_{y=1}^{B}}{\sum_{z=1}^{C}}{\left\lfloor{\frac{A}{x}}\right\rfloor}{\left\lfloor{\frac{B}{y}}\right\rfloor}{\left\lfloor{\frac{C}{z}}\right\rfloor}{\sum_{i|gcd(x,y)}}{\sum_{j|gcd(y,z)}}{\sum_{k|gcd(x,z)}}{\mu(i))}{\mu(j))}{\mu(k))}$
$={\sum_{i=1}^{A}}{\sum_{j=1}^{B}}{\sum_{k=1}^{A}}{\mu(x)}{\mu(y)}{\mu(z)}{\sum_{x|lcm(i,k)}}{\sum_{y|lcm(i,j)}}{\sum_{z|lcm(j,k)}}{\left \lfloor {\frac{A}{i}} \right \rfloor}{\left \lfloor {\frac{B}{j}} \right \rfloor}{\left \lfloor {\frac{C}{k}} \right \rfloor}$
将$\mu$不等于0的连边，双向改单向枚举三元环就好了。
代码：
#include<cstdio>
#include<vector>
#include<cstring>
#include<algorithm>
typedef long long lnt;
const int N=;
const lnt mod=(lnt)(1e9+);
struct edge{
int from;
int to;
int lcm;
}ed[N*];
struct ent{
int twd;
int lcm;
};
int prime[N];
int miu[N];
int ind[N];
bool vis[N];
lnt Lcm[N];
lnt F[][N];
int cnt;
std::vector<ent>hd[N];
int A,B,C;
void gtp(void)
{
miu[]=;
for(int i=;i<N;i++)
{
if(!vis[i])
{
prime[++cnt]=i;
miu[i]=-;
}
for(int j=;j<=cnt&&prime[j]*i<N;j++)
{
vis[i*prime[j]]=true;
if(i%prime[j]==)
break;
miu[i*prime[j]]=-miu[i];
}
}
return ;
}
lnt gcd(lnt x,lnt y)
{
if(!y)
return x;
return gcd(y,x%y);
}
int main()
{
int T;
gtp();
scanf("%d",&T);
while(T--)
{
int a,b,c;
scanf("%d%d%d",&a,&b,&c);
A=std::min(a,std::min(b,c));
C=std::max(a,std::max(b,c));
B=a+b+c-A-C;
cnt=;
for(int i=;i<=C;i++)
hd[i].clear(),ind[i]=;
for(int i=;i<=C;i++)
F[][i]=F[][i]=F[][i]=;
for(int i=;i<=A;i++)
for(int j=i;j<=A;j+=i)
F[][i]+=A/j;
for(int i=;i<=B;i++)
for(int j=i;j<=B;j+=i)
F[][i]+=B/j;
for(int i=;i<=C;i++)
for(int j=i;j<=C;j+=i)
F[][i]+=C/j;
lnt ans=;
for(int i=;i<=A;i++)
if(miu[i])
ans+=miu[i]*F[][i]*F[][i]*F[][i];
ans%=mod;
for(int d=;d<=C;d++)
{
for(int i=;i*d<=C;i++)
{
if(!miu[i*d])
continue;
for(int j=i+;1ll*j*i*d<=C;j++)
{
if(miu[j*d]==||gcd(j,i)!=)
continue;
int x=i*d,y=j*d,lcm=i*j*d;
ans+=miu[x]*(F[][y]*F[][lcm]*F[][lcm]+F[][y]*F[][lcm]*F[][lcm]+F[][y]*F[][lcm]*F[][lcm]);
ans=ans%mod;
ans+=miu[y]*(F[][x]*F[][lcm]*F[][lcm]+F[][x]*F[][lcm]*F[][lcm]+F[][x]*F[][lcm]*F[][lcm]);
ans=ans%=mod;
ind[x]++;
ind[y]++;
ed[++cnt]=(edge){x,y,lcm};
}
}
}
for(int i=;i<=cnt;i++)
{
int f=ed[i].from,t=ed[i].to,v=ed[i].lcm;
if(ind[f]<ind[t]||(ind[f]==ind[t]&&f<t))
hd[f].push_back((ent){t,v});
else
hd[t].push_back((ent){f,v});
}
for(int i=;i<=C;i++)
{
for(int j=;j<hd[i].size();j++)
Lcm[hd[i][j].twd]=hd[i][j].lcm;
for(int j=;j<hd[i].size();j++)
{
int a=i,b=hd[i][j].twd;
for(int k=;k<hd[b].size();k++)
{
int c=hd[b][k].twd;;
int lab=hd[a][j].lcm;
int lbc=hd[b][k].lcm;
int lac=Lcm[c];
if(!lac)
continue;
lnt tmp=miu[a]*miu[b]*miu[c];
lnt ttt=F[][lab]*F[][lbc]*F[][lac]+
F[][lab]*F[][lac]*F[][lbc]+
F[][lbc]*F[][lac]*F[][lab]+
F[][lbc]*F[][lab]*F[][lac]+
F[][lac]*F[][lab]*F[][lbc]+
F[][lac]*F[][lbc]*F[][lab];
ans=(ans+ttt*tmp%mod)%mod;
}
}
for(int j=;j<hd[i].size();j++)
Lcm[hd[i][j].twd]=;
}
printf("%lld\n",(ans%mod+mod)%mod);
}
return ;
}