### 题解 P4619 【[SDOI2018]旧试题】

posted on 2018-05-22 18:18:43 | under 题解 |

# $\text{760，741}$

## 正解

for(int i=alist[u];i;i=nxt[i]){}

#pragma GCC optimize(3)
#include<cstdio>
#include<algorithm>
#include<ctime>
#include<vector>
using namespace std;const int N=1e5+10;typedef long long ll;const ll mod=1e9+7;
const int E=1e6+10;const int U=1e5;int zhi[N];bool book[N];int miu[N];int hd;int T;int d[N];
int a;int b;int c;int l1;int l2;int l3;int lim;int fj[N][15];int tp[N];int st;int edt;
ll ret=0;int fa[N];int fc[N];int fb[N];struct data{int v;int val;};vector <data> ed[N];
inline int gcd(int a,int b){int c;while(b){c=a%b;a=b;b=c;}return a;}
int eu[E];int ev[E];int et[E];int fr;
inline void solve()
{
scanf("%d%d%d",&a,&b,&c);lim=max(max(a,b),c);st=clock();
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))%=mod;
for(int i=1;i<=b;i++)for(int j=1;j*i<=b;j++)(fb[i]+=b/(i*j))%=mod;
for(int i=1;i<=c;i++)for(int j=1;j*i<=c;j++)(fc[i]+=c/(i*j))%=mod;
for(int i=1;i<=lim;i++)//建图
{
if(miu[i]==0)continue;
for(int j=0;j<=(1<<tp[i])-1;j++)
{
int ret=1;for(int k=0,p=j;p;p>>=1,k++)if(p&1)ret*=fj[i][k];
for(int k=j;;k=(k-1)&j)
{
int g=1;for(int t=0,p=k;p;p>>=1,t++)if(p&1)g*=fj[i][t];
int v=(ll)i*g/ret;d[ret]++;d[v]++;
if(ret<v){eu[++fr]=ret;ev[fr]=v;et[fr]=i;}if(k==0)break;//去掉重边
}
}
}
for(int i=1;i<=fr;i++){if(d[eu[i]]<d[ev[i]])swap(eu[i],ev[i]);ed[eu[i]].push_back((data){ev[i],et[i]});}//变为有向边
vector <data> ::iterator it1,it2;
for(int u=1;u<=lim;u++)//vector存边
for(it1=ed[u].begin();it1!=ed[u].end();++it1)
for(it2=ed[it1->v].begin();it2!=ed[it1->v].end();++it2)
{
int v3;if((v3=(ll)it2->v*u/gcd(it2->v,u))>lim)continue;
int v1=it1->val;int v2=it2->val;
if(miu[u]*miu[it1->v]*miu[it2->v]==1)
{
(ret+=((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])%=mod;//处理三元环贡献，基本不能看了
}
else
{
(ret-=((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])%=mod;
ret>0?ret:ret+mod;
}
}
for(int i=1;i<=fr;i++)//有一个重复点的三元环
{
if(miu[eu[i]]==1)
(ret+=(ll)fa[et[i]]*fb[et[i]]%mod*fc[ev[i]]+(ll)fa[et[i]]*fb[ev[i]]%mod*fc[et[i]]+(ll)fa[ev[i]]*fb[et[i]]%mod*fc[et[i]])%=mod;
else
(ret-=(ll)fa[et[i]]*fb[et[i]]%mod*fc[ev[i]]+(ll)fa[et[i]]*fb[ev[i]]%mod*fc[et[i]]+(ll)fa[ev[i]]*fb[et[i]]%mod*fc[et[i]])%=mod;
ret=ret>0?ret:ret+mod;
if(miu[ev[i]]==1)
(ret+=(ll)fa[et[i]]*fb[et[i]]%mod*fc[eu[i]]+(ll)fa[et[i]]*fb[eu[i]]%mod*fc[et[i]]+(ll)fa[eu[i]]*fb[et[i]]%mod*fc[et[i]])%=mod;
else
(ret-=(ll)fa[et[i]]*fb[et[i]]%mod*fc[eu[i]]+(ll)fa[et[i]]*fb[eu[i]]%mod*fc[et[i]]+(ll)fa[eu[i]]*fb[et[i]]%mod*fc[et[i]])%=mod;
ret=ret>0?ret:ret+mod;
}
for(int i=1;i<=min(min(a,b),c);i++)//三个重复点的三元环
{
if(miu[i]==1)(ret+=(ll)fa[i]*fb[i]%mod*fc[i])%=mod;
else if(miu[i]==-1)(ret-=(ll)fa[i]*fb[i]%mod*fc[i])%=mod;ret=ret>0?ret:ret+mod;
}printf("%lld\n",ret);
}
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<=lim;i++){vector <data> emp;swap(emp,ed[i]);}
ret=0;fr=0;
}
int main()
{
miu[1]=1;for(int i=2;i<=U;i++)//线性筛莫比乌斯函数
{
if(book[i]==false){zhi[++hd]=i;miu[i]=-1;}
for(int j=1;j<=hd&&zhi[j]*i<=U;j++)
{book[i*zhi[j]]=true;if(i%zhi[j]==0){break;}miu[i*zhi[j]]=miu[i]*-1;}
}
for(int i=1;i<=hd;i++)//筛质因数分解
for(int j=1;j*zhi[i]<=U;j++)
{int nw=j*zhi[i];fj[nw][tp[nw]]=zhi[i];++tp[nw];}
scanf("%d",&T);for(int z=1;z<=T;z++){solve();clear();}return 0;//拜拜程序~
}