题目概述

Distance

解题报告

$i$ 走到 $j$ 不管怎么走，每个相差的素数都必须走一遍，所以：

$$ dis(i,j)=\sum_{p}p|e_{p,i}-e_{p,j}| $$

其中 $e_{p,i},e_{p,j}$ 表示 $i$ 中 $p$ 的幂次，$j$ 中 $p$ 的幂次，所以答案为：

$$ \sum_p p\sum_{i=1}^{n}\sum_{j=1}^{n}|e_{p,i}-e_{p,j}| $$

这种形式可以使用一种套路，令 $e_{p}<k$ 的数量为 $pre_{p,k}$ ，$e_p\ge k$ 的数量为 $suf_{p,k}$ ，则：

$$ \sum_{i=1}^{n}\sum_{j=1}^{n}|e_{p,i}-e_{p,j}|=2\sum_{k=1}^{\infty}pre_{p,k}suf_{p,k}=2\sum_{k=1}^{\infty}(n-\lfloor{n\over p^k}\rfloor)\lfloor{n\over p^k}\rfloor $$

这是因为 $e_{p,i},e_{p,j}(i<j)$ 会在枚举 $k$ 的过程中数到 $|e_{p,i}-e_{p,j}|$ 次。新的答案式子：

$$ 2\sum_p p\sum_{k=1}^{\infty}(n-\lfloor{n\over p^k}\rfloor)\lfloor{n\over p^k}\rfloor $$

不难发现，只有 $p\le \sqrt n$ 的时候，$k$ 才能 $>1$ ，所以我们先算出 $k=1$ ，然后暴力枚举 $\le \sqrt n$ 的素数即可。

$$ 2\sum_p p(n-\lfloor{n\over p}\rfloor)\lfloor{n\over p}\rfloor $$

考虑除法分块，这样 $(n-\lfloor{n\over p}\rfloor)\lfloor{n\over p}\rfloor$ 就是常数，只需要求 $\sum_{p\in[L,R]}p$ ，可以Min25求出。

由于Min25也是除法分块形式，因此只需要对 $n$ 做Min25，就可以得出所有 $[L,R]$ 的信息。

示例程序

#include<cmath>
#include<cstdio>
using namespace std;
typedef long long LL;
const int maxs=632454,MOD=1e9+7,INV2=MOD+1>>1;

LL n;int sum[maxs+5],ans;
int p[maxs+5];bool pri[maxs+5];
LL N,S,a[maxs+5],g[maxs+5],ID[2][maxs+5];

inline int ADD(int x,int y) {return x+y>=MOD?x+y-MOD:x+y;}
inline int MUL(int x,int y) {return (LL)x*y%MOD;}
void Make(int n){
    for (int i=2;i<=n;i++){
        if (!pri[i]) p[++p[0]]=i;
        for (int j=1,t;j<=p[0] && (t=i*p[j])<=n;j++)
            {pri[t]=true;if (!(i%p[j])) break;}
    }
    for (int i=1;i<=p[0];i++) sum[i]=ADD(sum[i-1],p[i]);
}
#define id(x) ((x)<=S?ID[0][x]:ID[1][N/(x)])
int Sum(LL L,LL R) {return MUL(MUL((L+R)%MOD,(R-L+1)%MOD),INV2);}
void Min25(LL n){
    int m=0;S=sqrt(n);N=n;
    for (LL l=1,r;l<=n;l=r+1){
        r=n/(n/l);a[++m]=n/l;g[m]=Sum(2,a[m]);
        a[m]<=S?ID[0][a[m]]=m:ID[1][n/a[m]]=m;
    }
    for (int j=1;j<=p[0] && p[j]<=S;j++)
        for (int i=1;i<=m && (LL)p[j]*p[j]<=a[i];i++)
            g[i]=ADD(g[i],MUL(p[j],ADD(sum[j-1],MOD-g[id(a[i]/p[j])])));
}
#define G(x) ((x)?g[id(x)]:0)
int main(){
    scanf("%lld",&n);
    Make(maxs);Min25(n);
    for (LL l=1,r;l<=n;l=r+1){
        LL x=n/l;r=n/x;
        int now=MUL(x%MOD,(n-x)%MOD);
        ans=ADD(ans,MUL(now,ADD(G(r),MOD-G(l-1))));
    }
    for (int i=1;i<=p[0] && (LL)p[i]*p[i]<=n;i++)
        for (LL pw=(LL)p[i]*p[i],x;pw<=n;pw*=p[i])
            x=n/pw,ans=ADD(ans,MUL(p[i],MUL(x%MOD,(n-x)%MOD)));
    printf("%d\n",(ans<<1)%MOD);
    return 0;
}