题目概述

Hasse Diagram

解题报告

考虑 $f(n)$ 的递推式，但是如果只考虑单个素数，很明显会数重复，因此一次性考虑完一个素数，即 $p^k$ 。

对于 $n\over p^k$ 的所有因子（即图中节点）都可以往前接上 $k$ 个节点（乘上 $p^i$ ），因此会多出 $kd({n\over p^k})$ 条边，$d(n)$ 表示 $n$ 的因子数。

除了这些边外，由于 $n\over p^k$ 还有其他素数，因此还有其他边。将 $n\over p^k$ 因子和往前接上的节点看作一条链，则这些链之间有 $f({n\over p^k})$ 条边，每条边都会使链中对应节点连上一条边，所以还多出了 $kf({n\over p^k})$ 条边。

算上原有的边，得出递推式：

$$ f(n)=(k+1)f({n\over p^k})+kd({n\over p^k}) $$

由于是枚举素数次幂的形式进行转移，因此可以Min25，只需要同时处理 $\sum f(n)$ 和 $\sum d(n)$ 即可：

$$ g_n=|\{p_i|p_i\le n\}|,d(p^k)=k+1,f(p^k)=k\\ Sd(a,b)=2g_a-\sum_{i=1}^{b-1}2+\sum_{i=b}\sum_{k=1}Sd(\lfloor{a\over p_i^k}\rfloor,i+1)(k+1)+(k+2)\\ Sf(a,b)=g_a-\sum_{i=1}^{b-1}1+\sum_{i=b}\sum_{k=1}Sf(\lfloor{a\over p_i^k}\rfloor,i+1)(k+1)+(k+1)+kSd(\lfloor{a\over p_i^k}\rfloor,i+1) $$

示例程序

#include<cmath>
#include<cstdio>
#include<algorithm>
#define fr first
#define sc second
#define mp make_pair
using namespace std;
typedef long long LL;
const int maxs=200000,MOD=1145140019,INV2=MOD+1>>1;

int te;LL n;
int p[maxs+5],sum[maxs+5];bool pri[maxs+5];
int S,m,ID[2][maxs+5];LL a[maxs+5],g[maxs+5],h[maxs+5];

#define ADD(x,y) (((x)+(y))%MOD)
#define MUL(x,y) ((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)])
pair<int,int> Sum(LL a,int b){
    if (a<1 || p[b]>a) return mp(0,0);
    int F=ADD(g[ID(a)],MOD-(b-1));
    int D=ADD(h[ID(a)],MOD-(b-1<<1));
    for (int i=b;i<=p[0] && (LL)p[i]*p[i]<=a;i++){
        LL A=p[i],B=A*A;
        for (int j=1;B<=a;j++,A=B,B=A*p[i]){
            pair<int,int> now=Sum(a/A,i+1);
            D=ADD(D,MUL(now.sc,j+1));D=ADD(D,j+2);
            F=ADD(F,MUL(now.fr,j+1));F=ADD(F,MUL(now.sc,j));
            F=ADD(F,j+1);
        }
    }
    return mp(F,D);
}
int Min25(LL x){
    n=x;S=sqrt(n);m=0;
    for (LL l=1,r;l<=n;l=r+1){
        r=n/(n/l);a[++m]=n/l;
        a[m]<=S?ID[0][a[m]]=m:ID[1][n/a[m]]=m;
        g[m]=(a[m]-1)%MOD;
    }
    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(MOD-1,ADD(g[ID(a[i]/p[j])],MOD-(j-1))));
    for (int i=1;i<=m;i++) h[i]=MUL(g[i],2);
    return Sum(n,1).fr;
}
int main(){
    Make(maxs);
    for (scanf("%d",&te);te;te--) scanf("%lld",&n),printf("%d\n",Min25(n));
    return 0;
}