题目
Ps：山东的题目可真(du)好(liu)，思维+码量的神仙题
推式
求\(\sum_{i=1}^A\sum_{j=1}^B\sum_{k=1}^Cd(ijk)\)
\(Ans=\sum_{i=1}^A\sum_{j=1}^B\sum_{k=1}^Cd(ijk)\)
\(~~~~~~~=\sum_{i=1}^{A}\sum_{j=1}^{B}\sum_{k=1}^{C}\sum_{d|i}\sum_{t|j}\sum_{p|k}\epsilon((d,t))\epsilon((t,p))\epsilon((d,p))\)
\(~~~~~~~=\sum_{i=1}^{A}\sum_{d|i}\sum_{j=1}^{B}\sum_{t|j}\sum_{k=1}^{C}\sum_{p|k}\epsilon((d,t))\epsilon((t,p))\epsilon((d,p))\)
\(~~~~~~~=\sum_{d=1}^{A}\sum_{i=1}^{\lfloor\frac{A}{d}\rfloor}\sum_{j=1}^{B}\sum_{t|j}\sum_{k=1}^{C}\sum_{p|k}\epsilon((d,t))\epsilon((t,p))\epsilon((d,p))\)
\(~~~~~~~=\sum_{d=1}^{A}\sum_{i=1}^{\lfloor\frac{A}{d}\rfloor}\sum_{t=1}^{B}\sum_{j=1}^{\lfloor\frac{B}{t}\rfloor}\sum_{p=1}^{C}\sum_{k=1}^{\lfloor\frac{C}
{p}\rfloor}\epsilon((d,t))\epsilon((t,p))\epsilon((d,p))\)
\(~~~~~~~=\sum_{d=1}^{A}\sum_{t=1}^{B}\sum_{p=1}^{C}\lfloor\frac{A}{d}\rfloor\lfloor\frac{B}{t}\rfloor\lfloor\frac{C}{p}\rfloor\epsilon((d,t))\epsilon((t,p))\epsilon((d,p))\)
\(~~~~~~~=\sum_{d=1}^{A}\sum_{t=1}^{B}\sum_{p=1}^{C}\lfloor\frac{A}{d}\rfloor\lfloor\frac{B}{t}\rfloor\lfloor\frac{C}{p}\rfloor\sum_{u|t\&u|d}\mu(u)\sum_{v|t\&v|p}\mu(v)\)
\(~~~~~~~~~~~~\sum_{w|d\&w|p}\mu(w)\)
\(~~~~~~~=\sum_{u=1}^{min(A,B)}\sum_{v=1}^{min(B,C)}\sum_{w=1}^{min(A,C)}\mu(u)\mu(v)\mu(w)\sum_{u|d\&w|d}\lfloor\frac{A}{d}\rfloor\sum_{u|t\&v|t}\lfloor\frac{B}{t}\rfloor\)
\(~~~~~~~~~~~~\sum_{v|p\&w|p}\lfloor\frac{C}{p}\rfloor\)
\(~~~~~~~=\sum_{u=1}^{min(A,B)}\sum_{v=1}^{min(B,C)}\sum_{w=1}^{min(A,C)}\mu(u)\mu(v)\mu(w)\sum_{lcm(u,w)|d}\lfloor\frac{A}{d}\rfloor\sum_{lcm(u,v)|t}\lfloor\frac{B}{t}\rfloor\)
\(~~~~~~~~~~~~\sum_{lcm(v,w)|p}\lfloor\frac{C}{p}\rfloor\)
\(~~~~~~~~~\)设有函数\(f(n,x)=\sum_{n|d}\lfloor\frac{x}{d}\rfloor\)
\(~~~~~~~=\sum_{u=1}^{min(A,B)}\sum_{v=1}^{min(B,C)}\sum_{w=1}^{min(A,C)}\mu(u)\mu(v)\mu(w)f(lcm(u,w),A)\)
\(~~~~~~~~~~~~f(lcm(u,v),B)f(lcm(v,w),C)\)
剪枝
对于\((u,v,w)\)这个三元组，我们考虑用三元环连边的方法剪枝：
显然：\(f(lcm(u,v),x)\)有效的条件为 \(\mu(u)*\mu(v)!=0\)且\(lcm(u,v)<x\)
那我们怎么连边呢？\(lcm(u,v)=u\cdot v \cdot gcd(u,v)\)，第一层枚举\(lcm(u,v)\)是肯定的
然后枚举\(u\)之后你会发现\(v\)不是唯一的，在范围内枚举再特判时间根本承受不住，那到底怎么做呢？
再枚举一层\(gcd(u,v)\)，从而得到\(v\)
没错，这是一个无向图，完全没必要嘛，定义成有向的，在建图的时候就特判\(u>v\)，强制有向
这时候是个无序三元组，只会出现一次
再加一个判断：大度点连向小度点，某dalao简单证明后时间复杂度\(O(m\sqrt m)\)
之前的一次特判：
保证了三元组无重复点，则最后要把此情况补上
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<iostream>
#include<vector>
using namespace std;
typedef long long LL;
const int maxn=1e5+9;
const int mexn=1e6+9;
const LL p=1e9+7;
inline int Read(){
int x(0),f(1); char c=getchar();
while(c<'0'||c>'9'){
if(c=='-') f=-1; c=getchar();
}
while(c>='0'&&c<='9')
x=(x<<3)+(x<<1)+c-'0',c=getchar();
return x*f;
}
int mu[maxn],prime[maxn];
int fj[maxn][20],tp[maxn];
bool visit[maxn];
inline int Gcd(int a,int b){
int c;
while(b){
c=a%b,a=b,b=c;
}
return a;
}
inline void F_phi(int n){
mu[1]=1; int tot(0);
for(int i=2;i<=n;++i){
if(!visit[i]){
prime[++tot]=i,
mu[i]=-1;
}
for(int j=1;j<=tot&&i*prime[j]<=n;++j){
visit[i*prime[j]]=true;
if(i%prime[j]==0)
break;
mu[i*prime[j]]=-mu[i];
}
}
for(int i=1;i<=tot;++i)
for(int j=1;j*prime[i]<=n;++j){
int num(j*prime[i]);
fj[num][tp[num]++]=prime[i];
}
}
struct node{
int to,d;
};
vector<node> edge[maxn];
int Up,A,B,C,cnt;
LL ans;
int fa[maxn],fb[maxn],fc[maxn],eu[mexn],ev[mexn],ed[mexn],du[maxn];
inline void Solve(){
Up=max(A,max(B,C));
if(A>B)
swap(A,B);
if(A>C)
swap(A,C);
if(B>C)
swap(B,C);
for(int i=1;i<=A;++i)
for(int j=1;j*i<=A;++j)
(fa[i]+=A/(i*j))%=p;
for(int i=1;i<=B;++i)
for(int j=1;j*i<=B;++j)
(fb[i]+=B/(i*j))%=p;
for(int i=1;i<=C;++i)
for(int j=1;j*i<=C;++j)
(fc[i]+=C/(i*j))%=p;
for(int i=1;i<=Up;++i){
if(mu[i]==0)
continue;
int tmp=(1<<tp[i])-1;
for(int j=0;j<=tmp;++j){
int u(1);
for(int k=0,ls=j;ls;ls>>=1,++k)
if(ls&1)
u*=fj[i][k];
for(int k=j;;k=(k-1)&j){
int g(1);
for(int t=0,ls=k;ls;ls>>=1,++t)
if(ls&1)
g*=fj[i][t];
int v=(LL)g*i/u;
++du[u],++du[v];
if(u<v){
eu[++cnt]=u,ev[cnt]=v,ed[cnt]=i;
}
if(k==0)
break;
}
}
}
for(int i=1;i<=cnt;++i){
if(du[eu[i]]<du[ev[i]])
swap(eu[i],ev[i]);
edge[eu[i]].push_back((node){ev[i],ed[i]});
}vector<node> ::iterator it1,it2;
int nn(0);
for(int u=1;u<=Up;++u){
for(it1=edge[u].begin();it1!=edge[u].end();++it1){
for(it2=edge[it1->to].begin();it2!=edge[it1->to].end();++it2){
int v3=(LL)it2->to*u/Gcd(it2->to,u);
if(v3>Up)//限制在范围内
continue;
++nn;
int v1=it1->d;int v2=it2->d;
if(mu[u]*mu[it1->to]*mu[it2->to]==1){
(ans+=((LL)fb[v2]*fc[v3]+(LL)fb[v3]*fc[v2]) *fa[v1]+
((LL)fb[v1]*fc[v3]+(LL)fb[v3]*fc[v1]) *fa[v2]+
((LL)fb[v2]*fc[v1]+(LL)fb[v1]*fc[v2]) *fa[v3])%=p;
}else {
(ans-=((LL)fb[v2]*fc[v3]+(LL)fb[v3]*fc[v2]) *fa[v1]+
((LL)fb[v1]*fc[v3]+(LL)fb[v3]*fc[v1]) *fa[v2]+
((LL)fb[v2]*fc[v1]+(LL)fb[v1]*fc[v2]) *fa[v3])%=p;
ans>0?ans:ans+p;
}
}
}/*
六种贡献，如果其中一个有序三元环在前三个sigma就不符合怎么办？
不符合的话在函数f中反正为0
*/
}
for(int i=1;i<=cnt;i++)//一个重复点的三元环
{
if(mu[eu[i]]==1)//two_v
{
(ans+=(LL)fa[ed[i]]*fb[ed[i]]%p*fc[ev[i]]%p+
(LL)fa[ed[i]]*fb[ev[i]]%p*fc[ed[i]]%p+
(LL)fa[ev[i]]*fb[ed[i]]%p*fc[ed[i]]%p)%=p;
}
else{
(ans-=(LL)fa[ed[i]]*fb[ed[i]]%p*fc[ev[i]]%p+
(LL)fa[ed[i]]*fb[ev[i]]%p*fc[ed[i]]%p+
(LL)fa[ev[i]]*fb[ed[i]]%p*fc[ed[i]]%p)%=p;
ans=ans>0?ans:ans+p;
}
if(mu[ev[i]]==1){
(ans+=(LL)fa[ed[i]]*fb[ed[i]]%p*fc[eu[i]]%p+
(LL)fa[ed[i]]*fb[eu[i]]%p*fc[ed[i]]%p+
(LL)fa[eu[i]]*fb[ed[i]]%p*fc[ed[i]]%p)%=p;
}
else{
(ans-=(LL)fa[ed[i]]*fb[ed[i]]%p*fc[eu[i]]%p+
(LL)fa[ed[i]]*fb[eu[i]]%p*fc[ed[i]]%p+
(LL)fa[eu[i]]*fb[ed[i]]%p*fc[ed[i]]%p)%=p;
ans=ans>0?ans:ans+p;
}
}
for(int i=1;i<=min(min(A,B),C);i++)//三个重复点的三元环
{
if(mu[i]==1)
(ans+=(LL)fa[i]*fb[i]%p*fc[i]%p)%=p;
else if(mu[i]==-1){
(ans-=(LL)fa[i]*fb[i]%p*fc[i]%p)%=p;
ans=ans>0?ans:ans+p;
}
}
printf("%lld\n",ans);
}
inline void Clear(){
for(int i=1;i<=A;i++)
fa[i]=0;
for(int i=1;i<=B;i++)
fb[i]=0;
for(int i=1;i<=C;i++)
fc[i]=0;
for(int i=1;i<=Up;i++){
vector<node> emp;
swap(emp,edge[i]);
du[i]=0;
}
ans=cnt=0;
}
int main(){
F_phi(100000);
int T=Read();
while(T--){
A=Read(),B=Read(),C=Read();
Solve();
Clear();
}
return 0;
}