P4619题解

· · 题解

一道智慧的反演题

好像不用三元图，纯数论也能过，但跑得有点小慢

前置芝士

1.莫比乌斯反演

2.整除分块

3.可以先做P3327

正题

众所周知，本题要我们求这个

\sum_{i=1}^{A}\sum_{j=1}^{B}\sum_{k=1}^{C}d(ijk)\bmod(1e9+7)

那么对于 d(ijk) 有这样浅显的性质

d(ijk)=\sum_{x|i}\sum_{y|j}\sum_{z|k}{[x \bot y]}{[x\bot z]}{[y\bot z]}

所以求这个

\sum_{i=1}^{A}\sum_{j=1}^{B}\sum_{k=1}^{C}\sum_{x|i}\sum_{y|j}\sum_{z|k}{[x \bot y]}{[x\bot z]}{[y\bot z]}

该枚举约树为枚举倍数

\sum_{x=1}^{A}\sum_{y=1}^{B}\sum_{z=1}^{C}{\left[ \frac{A}{x} \right]\left[ \frac{B}{y} \right]\left[ \frac{C}{z} \right]}{[x \bot y]}{[x\bot z]}{[y\bot z]}

然后我们挑一个 [y\bot z] 来反演（这里大家随意挑哪个）

\sum_{x=1}^{A}{\left[ \frac{A}{x} \right]}\sum_{y=1}^{B}\sum_{z=1}^{C}\left[ \frac{B}{y} \right][y \bot x]\left[ \frac{C}{z} \right][z \bot x]\sum_{d|z,d|y}{\mu(d)} \sum_{x=1}^{A}{\left[ \frac{A}{x} \right]}\sum^{\min(B,C)}_{d=1}{\mu(d)[d \bot x]}\sum^{\left[ \frac{B}{d} \right]}_{y=1}\sum^{\left[ \frac{C}{d} \right]}_{z=1}{\left[ \frac{B}{yd} \right][y\bot x]\left[ \frac{C}{zd} \right][z\bot x]}

以上我们走出了新手村，接下来的推导相当重要

我们令 f(n,x)=\sum_{d=1}^{n}\left[ \frac{n}{d} \right][d \bot x] 再令 g(n,x)=\sum_{d=1}^{n}{\mu(d)[d \bot x]}

\sum_{x=1}^{A}{\left[ \frac{A}{x} \right]}\sum_{}^{}{(g(r,x)-g(l-1,x))f(\left[ \frac{B}{d} \right],x)f(\left[ \frac{C}{d} \right],x)}

其中 l 和 r 是整除分块时的参数

接下来，我们考虑优化 f 和 g 的求法

重要性质：设 x_0 是只考虑 x 中不同素因子之后得到的数，与 x 互质和与 x_0互质等价，因此可以只考虑无平方因子。

那么对于 f 和 g 我们就可以根据以上性质得到以去掉某个素因子为递推关系的递推式

f(n,x)=f(\left[ \frac{n}{p} \right],x)-f(\left[ \frac{n}{p} \right],\frac{x}{p}) g(n,x)=g(n,\frac{x}{p})+g(\left[ \frac{x}{p} \right],x)

以上递推式其实也是数论体中的常见套路，可以用整除分块 O(\sqrt n) 搞出来，我看见有 dalao 写了关于它的证明， 而且我相当懒，就不写证明了

再用上一个小深搜就可以 AC 了

代码

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define reg register
const int N=2*1e5;
const int mod=1e9+7;
int vis[N],mul[N],d[N],saw[N],p[N],tot;
ll f[N][20],g[N][20],s[N],ans;
int T,A,B,C;

inline void ph(){
    mul[1]=1;
    d[1]=1;
    saw[1]=1;
    for(reg int i=2;i<N;i++){
        if(!vis[i]){
            p[++tot]=i;
            mul[i]=-1;
            d[i]=2;
            saw[i]=i;
        }
        for(reg int j=1;j<=tot&&p[j]*i<N;j++){
            vis[i*p[j]]=1;
            if(i%p[j]==0){
                d[i*p[j]]=(d[i]<<1)-d[i/p[j]];
                saw[i*p[j]]=saw[i];
                break;
            }
            d[i*p[j]]=d[i]<<1;
            saw[i*p[j]]=saw[i]*p[j];
            mul[i*p[j]]=-mul[i];
        }
    }
    for(reg int i=1;i<N;i++){
        d[i]+=d[i-1];
        mul[i]+=mul[i-1];
    }
//  for(int i=1;i<=100;i++){
//      printf("d--->%d mul---->%d\n",d[i],mul[i]);
//  }
}

inline void kasu(){
    g[0][1]=0;
    f[0][1]=0;
    for(reg int l=1,r;l<=A;++l){
        r=min(A/(A/l),B/(B/l));
        g[r][1]=mul[r];
        f[A/l][1]=d[A/l];
        f[B/l][1]=d[B/l];
        l=r;
    }
    memset(s,0,sizeof(s));
    for(reg int i=1;i<=C;i++){
        s[saw[i]]+=C/i;
    }
}

inline void reset(int x,int k){
    for(reg int l=1,r;l<=A;++l){
        r=min(A/(A/l),B/(B/l));
        g[r][k]=g[r][k-1]+g[r/x][k];
        f[A/l][k]=f[A/l][k-1]-f[(A/l)/x][k-1];
        f[B/l][k]=f[B/l][k-1]-f[(B/l)/x][k-1];
        l=r;
    }
}
inline void dfs(int re,int x,int k){
    ll res=0;
    for(reg int l=1,r;l<=A;++l){
        r=min(A/(A/l),B/(B/l));
        res+=((g[r][k]-g[l-1][k])*f[A/l][k]*f[B/l][k])%mod;
        res=(res%mod+mod)%mod;
        l=r;
    }
    ans+=(s[re]*res)%mod;
    ans%=mod;
    for(reg int i=x;1ll*p[i]*re<=C;i++){
        reset(p[i],k+1);
        dfs(re*p[i],i+1,k+1);
    }
    return ;
}

int main(){
    ios::sync_with_stdio(false);
    cin>>T;
    ph();
    while(T--){
        ans=0;
        cin>>A>>B>>C;
        if(A>B) swap(A,B);
        kasu();
        dfs(1,1,1);
        cout<<ans<<endl;
    }
    return 0;
}