[SDOI2018]旧试题

题目大意

给定\(A,B,C\)，求：
\[ \sum_{i=1}^A\sum_{j=1}^B\sum_{k=1}^C d(ijk)\ \ \ mod \ 10^9+7 \]

题解

\[ \sigma_0(ijk)=\sum_{x|i}\sum_{y|j}\sum_{z|k}[(x,y)==1][(x,z)==1][(y,z)==1] \]

那么我们的答案就是：
\[ \sum_{i=1}^a\sum_{j=1}^b\sum_{k=1}^c\sum_{x|i}\sum_{y|j}\sum_{z|k}[(x,y)==1][(x,z)==1][(y,z)==1] \]

\[ \sum_{x=1}^a\sum_{y=1}^b\sum_{z=1}^c\left \lfloor \frac{a}{x}\right \rfloor \left \lfloor \frac{b}{y}\right \rfloor\left \lfloor \frac{c}{z}\right \rfloor [(x,y)==1][(x,z)==1][(y,z)==1] \]

\[ \sum_{x=1}^a\sum_{y=1}^b\sum_{z=1}^c\left \lfloor \frac{a}{x}\right \rfloor \left \lfloor \frac{b}{y}\right \rfloor\left \lfloor \frac{c}{z}\right \rfloor \sum_{u|(x,y)}\mu(u)\sum_{v|(x,z)}\mu(v)\sum_{w|(y,z)}\mu(w) \]

\[ \sum_{u=1}^{min(x,y)}\sum_{v=1}^{min(x,z)}\sum_{w=1}^{min(y,z)}\mu(u)*\mu(v)*\mu(w)*\sum_{[u,v]|x}\frac{a}{x}\sum_{[u,w]|y}\frac{b}{y}\sum_{[v,w]|z}\frac{c}{z} \]

后面的东西我们可以预处理出来，现在我们需要考虑的是计算有序三元组\((u,v,w)\)产生的贡献。

通过打表找规律可以发现有用的边非常少，所以就可以三元环计数了。

然后我们还需要降低连边的复杂度。

我们先枚举三个元素相同的的情况。

通过看题解我们有一种枚举方式，枚举两个数的gcd，再去枚举两个数，并且要保证\(\mu(x)!=0\& \&\mu(y)!=0 \& \& (x/g,y/g)==1\)。

然后这样我们可以处理有两个元素相同的情况。

三元环计数

参考：https://www.luogu.org/blog/KingSann/fou-chang-yong-di-hei-ke-ji-san-yuan-huan-post

首先我们要给无向图定向，我们先强制规定一下顺序，就是度数小的向度数大的连边，如果一样，就按照编号大小连边。

这样一定会连出一个\(DAG\)。

然后统计答案的方法就是枚举点\(u\)，将\(u\)的所有出边都标记一下。

再去枚举\(u\)的出点的出点，如果这个出点是\(u\)那么这就是一个三元环。

这样可以保证每个三元环只会被统计一次。

再去考虑复杂度。
\[ \sum_{i=1}^m out[to_i] \]
考虑这个东西的级别。

当\(out[to_i]\geq \sqrt m\)时，因为一共只有\(m\)条边，这样的点本身只有\(\sqrt m\)个，所以复杂度上界是\(m \sqrt m\)。

当\(out[to_i]<\sqrt m\)时，最多会有\(n\)个点连向它，所以复杂度上界是\(n\sqrt m\)的 。

然后就做完了。

这题还有一个\(trick\),就是只需要在最后取模。

代码

#include<bits/stdc++.h>
#define N 100009
using namespace std;
typedef long long ll;
const int maxn=100000;
const int mod=1e9+7;
int mu[N],prime[N],T,du[N];
ll fa[N],fb[N],fc[N],a,b,c,ans,val[N],tag[N];
bool vis[N];
inline ll rd(){
    ll x=0;char c=getchar();bool f=0;
    while(!isdigit(c)){if(c=='-')f=1;c=getchar();}
    while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=getchar();}
    return f?-x:x;
}
inline void MOD(ll &x){x=x>=mod?x-mod:x;}
inline void MOD(int &x){x=x>=mod?x-mod:x;}
int gcd(int a,int b){return b?gcd(b,a%b):a;}
inline void prework(){
    mu[1]=1;
    int k;
    for(int i=2;i<=maxn;++i){
        if(!vis[i]){prime[++prime[0]]=i;mu[i]=-1;}
        for(int j=1;j<=prime[0]&&(k=i*prime[j])<=maxn;++j){
            vis[k]=1;
            if(i%prime[j]==0){mu[k]=0;break;}
            mu[k]=-mu[i];
        }
    }
}
struct edge{int u,v;ll val;};
vector<edge>vec;
vector<edge>::iterator it;
struct node{int to;ll val;};
vector<node>ed[N];
vector<node>::iterator it2,it3;
int main(){
    prework();
    T=rd();
    while(T--){
        a=rd();b=rd();c=rd();
        vec.clear();
        int mx=max(max(a,b),c);
        int mi=min(min(a,b),c);
        memset(fa,0,sizeof(fa));
        memset(fb,0,sizeof(fb));
        memset(fc,0,sizeof(fc));
        memset(du,0,sizeof(du));
        ans=0;
        for(int i=1;i<=a;++i)
          for(int j=i;j<=a;j+=i)fa[i]+=a/j;
        for(int i=1;i<=b;++i)
          for(int j=i;j<=b;j+=i)fb[i]+=b/j;
        for(int i=1;i<=c;++i)
          for(int j=i;j<=c;j+=i)fc[i]+=c/j;
        for(int i=1;i<=mi;++i)if(mu[i]){
            ans+=mu[i]*mu[i]*mu[i]*fa[i]*fb[i]*fc[i];
        }
        for(int g=1;g<=mx;++g)
          for(int i=1;i*g<=mx;++i)if(mu[i*g])
            for(int j=i+1;1ll*i*j*g<=mx;++j)if(mu[j*g]&&gcd(i,j)==1){
                int x=i*g,y=j*g;ll z=i*g*j;
                int xx=mu[x]*mu[x]*mu[y],yy=mu[x]*mu[y]*mu[y];
                ans+=xx*(fa[x]*fb[z]*fc[z]+fa[z]*fb[x]*fc[z]+fa[z]*fb[z]*fc[x]);
                ans+=yy*(fa[y]*fb[z]*fc[z]+fa[z]*fb[y]*fc[z]+fa[z]*fb[z]*fc[y]);
                du[x]++;du[y]++;
                vec.push_back(edge{x,y,z});
            }
        for(it=vec.begin();it!=vec.end();++it){
            edge x=*it;
            if(du[x.u]<du[x.v])swap(x.u,x.v);
            else if(du[x.u]==du[x.v]&&x.u>x.v)swap(x.u,x.v);
            ed[x.u].push_back(node{x.v,x.val}); 
        }
        for(int i=1;i<=mx;++i){
            for(it2=ed[i].begin();it2!=ed[i].end();++it2){
                node x=*it2;
                tag[x.to]=i;
                val[x.to]=x.val;
            }
            for(it2=ed[i].begin();it2!=ed[i].end();++it2){
                node x=*it2;
                for(it3=ed[x.to].begin();it3!=ed[x.to].end();++it3){
                    node y=*it3;
                    if(tag[y.to]!=i)continue;
                    ll xx=val[y.to],yy=x.val,zz=y.val,tg=mu[i]*mu[x.to]*mu[y.to];
                    ans+=tg*(fa[xx]*fb[yy]*fc[zz]+
                             fa[yy]*fb[zz]*fc[xx]+
                             fa[xx]*fb[zz]*fc[yy]+
                             fa[yy]*fb[xx]*fc[zz]+
                             fa[zz]*fb[xx]*fc[yy]+
                             fa[zz]*fb[yy]*fc[xx]);
                }
            }   
        }
        for(int i=1;i<=mx;++i)ed[i].clear();
        printf("%lld\n",ans%mod);
    }
    return 0;
}

这样我们枚举的复杂度就是\(m\sqrt m\)。

[SDOI2018]旧试题

原文：https://www.cnblogs.com/ZH-comld/p/10827004.html