题解

1 条题解

  • 0
    @ 2018-10-07 10:51:43

    #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;//拜拜程序~
    }

  • 1

信息

ID
2049
难度
9
分类
(无)
标签
递交数
6
已通过
4
通过率
67%
上传者