题目大意：
求
题解：
大毒瘤。
先反演：
然后套路处理后面那三坨为fa,fb,fc。
为了速度，我们可以直接枚举lcm，将μi!=0&&μj!=0之间建一条边权为lcm(i,j)的边。
如果(u,v,w)这个三元组合法的话：
- 三者互不相同。此时应形成一个三元环。
- 两项相同。此时有一条边即可。
- 三项相同。此时枚举所有的点即可。
代码：
#include<vector> #include<cstdio> #include<cstring> #include<algorithm> using namespace std; #define N 100050 #define MOD 1000000007 #define ll long long ll pri[N],cnt,mu[N],ft[N][10],mem[N],T,a,b,c; bool vis[N]; ll fa[N],fb[N],fc[N]; void init() { mu[1]=1; for(register ll i=2;i<=100000;i++) { if(!vis[i]) { mu[i]=-1; pri[++cnt]=i; } for(register ll j=1;i*pri[j]<=100000;j++) { vis[i*pri[j]]=1; if(i%pri[j])mu[i*pri[j]]=-mu[i]; else break; } } for(register ll i=1;i<=cnt;i++) { for(register ll j=1;j*pri[i]<=100000;j++) { mem[pri[i]*j]++; ft[pri[i]*j][mem[pri[i]*j]]=pri[i]; } } } struct Pair { ll x,v; Pair(){} Pair(ll x,ll v):x(x),v(v){}; }; vector<Pair>ve[N]; ll d[N]; void initt() { for(register ll i=1;i<=a;i++)fa[i]=0; for(register ll i=1;i<=b;i++)fb[i]=0; for(register ll i=1;i<=c;i++)fc[i]=0; for(register ll i=1;i<=c;i++) { vector<Pair>tmp; swap(ve[i],tmp); d[i]=0; } } ll hs[N]; struct EG { ll f,t,v; }e[10*N]; ll sol() { if(a>b)swap(a,b); if(a>c)swap(a,c); if(b>c)swap(b,c); for(register ll i=1;i<=a;i++) for(register ll j=1;i*j<=a;j++) { fa[i]+=(a/(i*j)); if(fa[i]>MOD)fa[i]-=MOD; } for(register ll i=1;i<=b;i++) for(register ll j=1;i*j<=b;j++) { fb[i]+=(b/(i*j)); if(fb[i]>MOD)fb[i]-=MOD; } for(register ll i=1;i<=c;i++) for(register ll j=1;i*j<=c;j++) { fc[i]+=(c/(i*j)); if(fc[i]>MOD)fc[i]-=MOD; } ll ct=0; for(register ll i=1;i<=c;i++)//lcm { if(!mu[i])continue; for(register ll j=0;j<(1<<mem[i]);j++) { ll u = 1; for(register ll k=1;k<=mem[i];k++) if((j>>(k-1))&1) u*=ft[i][k]; for(register ll k = j;;k=(k-1)&j) { ll v = i/u; for(register ll w=1;w<=mem[i];w++) if((k>>(w-1))&1) v*=ft[i][w]; if(u>v) { d[u]++,d[v]++,ct++; e[ct].f=u,e[ct].t=v,e[ct].v=i; } if(!k)break; } } } for(register ll i=1;i<=ct;i++) { if(d[e[i].f]<d[e[i].t]) swap(e[i].f,e[i].t); ve[e[i].f].push_back(Pair(e[i].t,e[i].v)); } ll ret = 0; ll p1,p2,p3,v1,v2,v3,kk; for(register ll i=1;i<=b;i++) { if(!mu[i])continue; //abc for(register ll j=0;j<ve[i].size();j++) hs[ve[i][j].x]=ve[i][j].v; for(register ll j=0;j<ve[i].size();j++) { for(register ll k=0;k<ve[ve[i][j].x].size();k++) { if(hs[ve[ve[i][j].x][k].x]&&ve[i][j].x!=ve[ve[i][j].x][k].x) { p1=i,p2=ve[i][j].x,p3=ve[p2][k].x; v1 = ve[p1][j].v;v2 = ve[p2][k].v;v3 = hs[p3]; kk = mu[p1]*mu[p2]*mu[p3]; ret = (ret+kk*fa[v1]*fb[v2]*fc[v3])%MOD; ret = (ret+kk*fa[v1]*fb[v3]*fc[v2])%MOD; ret = (ret+kk*fa[v2]*fb[v1]*fc[v3])%MOD; if(ret<0)ret+=MOD; ret = (ret+kk*fa[v2]*fb[v3]*fc[v1])%MOD; ret = (ret+kk*fa[v3]*fb[v1]*fc[v2])%MOD; ret = (ret+kk*fa[v3]*fb[v2]*fc[v1])%MOD; if(ret<0)ret+=MOD; } } } for(register ll j=0;j<ve[i].size();j++) hs[ve[i][j].x]=0; //aab abb for(register ll j=0;j<ve[i].size();j++) { ll to = ve[i][j].x; kk=mu[i]; p1=i,p2=to,p3=p2; v1 = ve[p1][j].v;v2 = p2;v3 = v1; ret = (ret+kk*fa[v3]*fb[v1]*fc[v2])%MOD; ret = (ret+kk*fa[v2]*fb[v3]*fc[v1])%MOD; ret = (ret+kk*fa[v1]*fb[v2]*fc[v3])%MOD; if(ret<0)ret+=MOD; kk=mu[to]; p1=i,p2=to,p3=p1; v1 = ve[p1][j].v;v2 = v1;v3 = p1; ret = (ret+kk*fa[v3]*fb[v1]*fc[v2])%MOD; ret = (ret+kk*fa[v2]*fb[v3]*fc[v1])%MOD; ret = (ret+kk*fa[v1]*fb[v2]*fc[v3])%MOD; if(ret<0)ret+=MOD; } //aaa ret = (ret+mu[i]*fa[i]*fb[i]*fc[i])%MOD; if(ret<0)ret+=MOD; } return ret; } int main() { init(); scanf("%lld",&T); while(T--) { scanf("%lld%lld%lld",&a,&b,&c); printf("%lld ",sol()); initt(); } return 0; }