反演+三元环计数+卡常
反演部分：
第一步还是“约数个数和”那个结论的扩展：（考虑质数的次数的分配即可证明）
最后一步就是枚举u,v,w考虑满足能凑出u，v，w的x,y,z有哪些
（式子u,v,w,lcm那里有打错了）
还是一脸不可做
三个点形成的三元组(u,v,w)贡献一定。
三元环计数！
首先埃拉托尼斯筛把后面三个括号，每个lcm贡献搞出来。之后可以O(1)计算
两个点如果miu(u),miu(v)都是非零的，且lcm<=max(a,b,c)连接lcm(u,v)的边权的边。
统计每个三元环的贡献即可
O(m)建边：
枚举lcm为i
miu(u),miu(v)都是非零的，所以miu(lcm(u,v))也是非零的
枚举i的约数a（就是2^k啦，k是质因子个数），再枚举a的约数g，b=(long long)i*g/a
连接(a,b)即可。（容易证明，这个b一定满足gcd(a,b)=g,lcm(a,b)=i）
一共大概76万条边
三元环计数是O(msqrt(m))的
卡常：
1.vector存边。利于缓存
2.枚举约数a,g用状压别dfs
3.这题答案不爆long long所以最后%mod 即可
#include<bits/stdc++.h> #define reg register int #define il inline #define fi first #define se second #define mk(a,b) make_pair(a,b) #define numb (ch^'0') using namespace std; typedef long long ll; template<class T>il void rd(T &x){ char ch;x=0;bool fl=false; while(!isdigit(ch=getchar()))(ch=='-')&&(fl=true); for(x=numb;isdigit(ch=getchar());x=x*10+numb); (fl==true)&&(x=-x); } template<class T>il void ot(T x){x/10?ot(x/10):putchar(x%10+'0');} template<class T>il void prt(T a[],int st,int nd){for(reg i=st;i<=nd;++i) printf("%lld ",a[i]);putchar(' ');} namespace Miracle{ const int N=1e5+5; const int mod=1e9+7; int A,B,C; int du[N]; vector<int>yin[N],to[N]; vector<int>val[N]; int bian[N*20][3]; int cnt; ll con[N][3];//A/x B/y C/z int miu[N],pri[N],tot; int vis[N]; int wei[N]; ll ans; void sieve(int n){ miu[1]=1; for(reg i=2;i<=n;++i){ if(!vis[i]){ pri[++tot]=i; miu[i]=-1; } for(reg j=1;j<=tot;++j){ if(pri[j]*i>n) break; vis[pri[j]*i]=1; if(i%pri[j]==0){ miu[i*pri[j]]=0; break; } miu[i*pri[j]]=-miu[i]; } } for(reg j=1;j<=tot;++j){ for(reg i=pri[j];i<=n;i+=pri[j]){ yin[i].push_back(pri[j]); } } } ll huan(int a,int b,int c,int ab,int bc,int ac){ ll ret=0; ret= (ll)miu[a]*miu[b]*miu[c]*( (ll)con[ab][0]*con[bc][1]*con[ac][2]+ (ll)con[ac][0]*con[bc][1]*con[ab][2]+ (ll)con[ab][0]*con[ac][1]*con[bc][2]+ (ll)con[bc][0]*con[ac][1]*con[ab][2]+ (ll)con[ac][0]*con[ab][1]*con[bc][2]+ (ll)con[bc][0]*con[ab][1]*con[ac][2] ); return ret; } void pre(int n){ for(reg i=1;i<=n;++i){ for(reg j=i;j<=n;j+=i){ con[i][0]+=A/j; con[i][1]+=B/j; con[i][2]+=C/j; } } for(reg i=1;i<=n;++i){ ans+=(ll)miu[i]*miu[i]*miu[i]*con[i][0]*con[i][1]*con[i][2]; // cout<<" after "<<i<<" : "<<ans<<endl; } for(reg i=2;i<=n;++i){ if(miu[i]!=0){ for(reg j=0;j<(int)(1<<yin[i].size());++j){ int a=1; for(reg l=0;l<(int)yin[i].size();++l) if(j&(1<<l)) a*=yin[i][l]; // cout<<" j "<<j<<" "<<a<<endl; for(reg k=0;k<(1<<yin[a].size());++k){ int gcd=1; for(reg l=0;l<(int)yin[a].size();++l) if(k&(1<<l)) gcd*=yin[a][l]; int b=(ll)i*gcd/a; // cout<<" k "<<k<<" "<<gcd<<" "<<b<<endl; if(a<b){ /// cout<<" addedge "<<a<<" "<<b<<endl; bian[++cnt][0]=a; bian[cnt][1]=b; bian[cnt][2]=i; ++du[a];++du[b]; ans+= (ll)miu[a]*miu[a]*miu[b]*con[a][0]*con[i][1]*con[i][2]+ (ll)miu[a]*miu[a]*miu[b]*con[i][0]*con[a][1]*con[i][2]+ (ll)miu[a]*miu[a]*miu[b]*con[i][0]*con[i][1]*con[a][2]+ (ll)miu[a]*miu[b]*miu[b]*con[b][0]*con[i][1]*con[i][2]+ (ll)miu[a]*miu[b]*miu[b]*con[i][0]*con[b][1]*con[i][2]+ (ll)miu[a]*miu[b]*miu[b]*con[i][0]*con[i][1]*con[b][2]; } } } } } } void clear(int n){ ans=0; memset(du,0,sizeof du); memset(con,0,sizeof con); memset(vis,0,sizeof vis); memset(wei,0,sizeof wei); for(reg i=1;i<=n;++i) to[i].clear(),val[i].clear(); cnt=0; } int main(){ int t; rd(t); sieve(N-3); memset(vis,0,sizeof vis); while(t--){ rd(A);rd(B);rd(C); int n=max(A,max(B,C)); pre(n); // cout<<" ans1 "<<ans<<endl; for(reg i=1;i<=cnt;++i){ int x=bian[i][0],y=bian[i][1]; if(du[x]<du[y]) swap(x,y); to[x].push_back(y); val[x].push_back(bian[i][2]); } for(reg i=1;i<=n;++i){ for(reg j=0;j<(int)to[i].size();++j){ int y=to[i][j]; vis[y]=i; wei[y]=val[i][j]; } for(reg j=0;j<(int)to[i].size();++j){ int y=to[i][j]; for(reg k=0;k<(int)to[y].size();++k){ int z=to[y][k]; if(vis[z]==i){ ans+=huan(i,y,z,val[i][j],val[y][k],wei[z]); } } } } ans%=mod; printf("%lld ",ans); clear(n); } return 0; } } signed main(){ Miracle::main(); return 0; } /* Author: *Miracle* Date: 2019/3/8 18:46:49 */
其实全都是套路。。。。