传送门

Description

\[\sum_{i=1}^A\sum_{j=1}^B\sum_{k=1}^Cd(ijk) (\mathrm{mod\:} 10^9+7)
\]

其中 \(d(ijk)\) 表示 \(i × j × k\)的约数个数。

Solution

首先，有一个公式

\[σ_0(n_1n_2···n_m) =\sum_{a_1|n_1}\sum_{a_2|n_2}···\sum_{a_m|n_m}\prod_{1≤i \neq j≤m} [a_i ⊥ a_j]
\]

所以，我们就可以把答案反演成：

\[\sum_{u=1}^{M}\sum_{v=1}^{M}\sum_{w=1}^{M}\mu(u)\mu(v)\mu(w)\left ( \sum_{lcm(u,v)|x}\frac{A}{x} \right )\left ( \sum_{lcm(v,w)|y}\frac{B}{y} \right )\left ( \sum_{lcm(u,w)|z}\frac{C}{z} \right )
\]

其中,\(M=max\{ A,B,C\}\)

我们发现，根据调和级数，可以求出后面的那些都可以通过\(O(n\log n)\)预处理出来

我们先直接计算\(u=v=w\)以及\(u,v,w\)中恰有两个数相等的情况

然后剩下的就是\(u,v,w\)互不相同的了，我们把\(lcm(u,v)\leq M\)的\(u,v\)连边，这样，其实就是求所有三元环的贡献啦。

关于求三元环呢，这里有个不常用的黑科技，参见这里,可以使得复杂度为\(O(m\sqrt m)\)

其实图的边数是比较少的，所以目测能过

据说用\(vector\)要比较快？

Code 

#include<bits/stdc++.h>

#define ll long long

#define max(a,b) ((a)>(b)?(a):(b))

#define min(a,b) ((a)<(b)?(a):(b))

inline int read()

{

    int x=0,f=1;char ch=getchar();

    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}

    while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();}

    return x*f;

}

#define MN 200005

#define mN 100005

#define mod 1000000007

int mu[mN],pr[mN/10],tot;bool mark[mN];

int gcd(int x,int y){return y?gcd(y,x%y):x;}

inline void init_mu()

{

    mu[1]=1;register int i,j;

    for(i=2;i<mN;++i)

    {

        if(!mark[i]){pr[++tot]=i;mu[i]=-1;}

        for(j=1;j<=tot&&pr[j]*i<mN;++j)

        {

            mark[pr[j]*i]=true;

            if(i%pr[j]) mu[pr[j]*i]=-mu[i];

            else{mu[pr[j]*i]=0;break;}

        }

    }

}

int T,A,B,C,N,M;

ll fa[MN],fb[MN],fc[MN],ans;

struct edge{int to,lcm;};

struct Edge{int f,t,lcm;}e[MN<<4];int en;

std::vector<edge> G[mN];

int d[mN],mrk[mN];

inline void init()

{

    register int i,j;N=max(A,max(B,C));M=min(A,min(B,C));

    memset(d,0,sizeof d);en=0;for(i=1;i<=N;++i)G[i].clear();ans=0;

    memset(fa,0,sizeof fa);memset(fb,0,sizeof fb);memset(fc,0,sizeof fc);

    for(i=1;i<=A;++i) for(j=i;j<=A;j+=i) fa[i]+=A/j;

    for(i=1;i<=B;++i) for(j=i;j<=B;j+=i) fb[i]+=B/j;

    for(i=1;i<=C;++i) for(j=i;j<=C;j+=i) fc[i]+=C/j;

}

#define C(x,y,z) (fa[x]*fb[y]*fc[z])

#define cal(x,y,z) (C(x,y,z)+C(x,z,y)+C(y,x,z)+C(y,z,x)+C(z,x,y)+C(z,y,x))

int main()

{

    register int g,i,j,k,x,y,w;

    T=read();init_mu();

    while(T--)

    {

        A=read();B=read();C=read();init();

        for(i=1;i<=M;++i)if(mu[i])ans+=mu[i]*mu[i]*mu[i]*fa[i]*fb[i]*fc[i];

        for(g=1;g<=N;++g)for(i=1;i*g<=N;++i)if(mu[i*g])for(j=i+1;1ll*i*j*g<=N;++j)if(mu[j*g]&&gcd(i,j)==1)

        {

            x=i*g;y=j*g;++d[x];++d[y];e[++en]=(Edge){x,y,x*j};w=x*j;

            ans+=1ll*mu[x]*mu[x]*mu[y]*(fa[x]*fb[w]*fc[w]+fa[w]*fb[x]*fc[w]+fa[w]*fb[w]*fc[x]);

            ans+=1ll*mu[x]*mu[y]*mu[y]*(fa[y]*fb[w]*fc[w]+fa[w]*fb[y]*fc[w]+fa[w]*fb[w]*fc[y]);

        }

        for(i=1;i<=en;++i)

            if(d[e[i].f]>d[e[i].t]||(d[e[i].f]==d[e[i].t]&&e[i].f<e[i].t)) G[e[i].f].push_back((edge){e[i].t,e[i].lcm});

            else G[e[i].t].push_back((edge){e[i].f,e[i].lcm});

        for(i=1;i<=N;++i)

        {

            for(j=G[i].size()-1;~j;--j) mrk[G[i][j].to]=G[i][j].lcm;

            for(j=G[i].size()-1;~j;--j)

            {

                x=G[i][j].to;register int ix=G[i][j].lcm,iy;

                for(k=G[x].size()-1;~k;--k)if(iy=mrk[y=G[x][k].to])

                {

                    register int xy=G[x][k].lcm;

                    ans+=mu[i]*mu[x]*mu[y]*cal(ix,iy,xy);

                }

            }

            for(j=G[i].size()-1;~j;--j) mrk[G[i][j].to]=0;

        }

        printf("%lld\n",ans%mod);

    }

}

Blog来自PaperCloud，未经允许，请勿转载，TKS！