# bzoj 2693 jzptab / 洛谷 P1829 Crash的数字表格 题解【莫比乌斯反演】【狄利克雷卷积】

## Description

$$\sum_{i=1}^n\sum_{j=1}^m\operatorname{lcm}(i,j)$$

## Output

$latex T$ 行 每行一个整数 表示第i组数据的结果

1
4 5

122

## HINT

$latex T\le 10000$

$latex N, M\le 10000000​$

## 题解：

$latex \operatorname{lcm}$ 和 $latex \gcd$ 关系很近，因此在反演中有可能有较大联系。要尽可能把 $latex \operatorname{lcm}$ 转化为 $latex \gcd$。

$$\sum_{i=1}^n\sum_{j=1}^m\operatorname{lcm}(i,j)$$

\begin{aligned} \text{原式}&=\sum_{i=1}^a\sum_{j=1}^b\operatorname{lcm}(i,j)\\ &=\sum_{i=1}^a\sum_{j=1}^b\frac{ij}{\gcd(i,j)} \end{aligned}

$$\sum_{k=1}^{a}\sum_{i=1}^a\sum_{j=1}^b[\gcd(i,j)=k]\frac{ij}k$$

$$\sum_{k=1}^a\frac 1k\sum_{i=1}^a\sum_{j=1}^b[\gcd(i,j)=k]ij$$

\begin{aligned} &\sum_{k=1}^a\frac 1k\sum_{i=1}^\left\lfloor\frac ak\right\rfloor\sum_{j=1}^\left\lfloor\frac bk\right\rfloor[\gcd(i,j)=1]ijk^2\\ =&\sum_{k=1}^ak\sum_{i=1}^\left\lfloor\frac ak\right\rfloor\sum_{j=1}^\left\lfloor\frac bk\right\rfloor[\gcd(i,j)=1]ij \end{aligned}

$$f(n)=\sum_{i=1}^\left\lfloor\frac ak\right\rfloor\sum_{j=1}^\left\lfloor\frac bk\right\rfloor[\gcd(i,j)=n]ij$$

\begin{aligned} g(n)&=\sum_{n|d}f(d)\\ &=\sum_{i=1}^\left\lfloor\frac ak\right\rfloor\sum_{j=1}^\left\lfloor\frac bk\right\rfloor[\gcd(i,j)=n,2n,3n,\cdots]ij\\ &=\sum_{i=1}^\left\lfloor\frac ak\right\rfloor\sum_{j=1}^\left\lfloor\frac bk\right\rfloor[n|\gcd(i,j)]ij \end{aligned}

$$g(n)=\sum_{i=1}^\left\lfloor\frac a{kn}\right\rfloor\sum_{j=1}^\left\lfloor\frac b{kn}\right\rfloor[1|\gcd(i,j)]ij$$

$$(1+2+\cdots+\left\lfloor\frac a{kn}\right\rfloor)\times(1+2+\cdots+\left\lfloor\frac b{kn}\right\rfloor)=\frac{\left\lfloor\frac a{kn}\right\rfloor(\left\lfloor\frac a{kn}\right\rfloor+1)\left\lfloor\frac b{kn}\right\rfloor(\left\lfloor\frac b{kn}\right\rfloor+1)}{4}$$

\begin{aligned} f(n)&=\sum_{n|d}\mu\left(\frac dn\right)g(d)\\ &=\sum_{i=1}^\left\lfloor\frac ak\right\rfloor\mu(i)g(ni) \end{aligned}

\begin{aligned} f(1)&=\sum_{i=1}^\left\lfloor\frac ak\right\rfloor\mu(i)g(i)\\ &=\sum_{i=1}^\left\lfloor\frac ak\right\rfloor\mu(i)i^2\frac{\left\lfloor\frac a{ki}\right\rfloor\left(\left\lfloor\frac a{ki}\right\rfloor+1\right)\left\lfloor\frac b{ki}\right\rfloor\left(\left\lfloor\frac b{ki}\right\rfloor+1\right)}{4} \end{aligned}

$$\sum_{k=1}^ak\sum_{i=1}^\left\lfloor\frac ak\right\rfloor\mu(i)i^2\frac{\left\lfloor\frac a{ki}\right\rfloor\left(\left\lfloor\frac a{ki}\right\rfloor+1\right)\left\lfloor\frac b{ki}\right\rfloor\left(\left\lfloor\frac b{ki}\right\rfloor+1\right)}{4}$$

$$S(n)=\frac{n(n+1)}2$$

$$\sum_{k=1}^a\sum_{i=1}^\left\lfloor\frac ak\right\rfloor k\mu(i)i^2S\left(\left\lfloor\frac a{ki}\right\rfloor\right)S\left(\left\lfloor\frac b{ki}\right\rfloor\right)$$

$$\sum_{T=1}^a\sum_{d|T}Td\mu(d)S\left(\left\lfloor\frac aT\right\rfloor\right)S\left(\left\lfloor\frac bT\right\rfloor\right)$$

$$\sum_{T=1}^aS\left(\left\lfloor\frac aT\right\rfloor\right)S\left(\left\lfloor\frac bT\right\rfloor\right)\sum_{d|T}Td\mu(d)$$

\begin{aligned} f(T)&=\sum_{d|T}Td\mu(d)\\ &=\sum_{d|T}\frac Td d^2\mu(d) \end{aligned}

$$\sum_{T=1}^aS\left(\left\lfloor\frac aT\right\rfloor\right)S\left(\left\lfloor\frac bT\right\rfloor\right)f(T)$$

## Code：

#include<cstdio>
#include<cstring>
#define p 100000009
int Min(int x,int y){return x<y?x:y;}
int Plus(int x,int y){return x+y>=p?x+y-p:x+y;}
int Mul(int x,int y){return 1ll*x*y%p;}
int pri[10001000],f[10001000],cnt=0;
bool is[10001000];
int main()
{
is[0]=is[1]=1;
f[1]=1;
for(int i=2;i<=10000000;++i)
{
if(!is[i])
{
pri[++cnt]=i;
f[i]=Plus(i,p-Mul(i,i));
}
for(int j=1;j<=cnt&&i*pri[j]<=10000000;++j)
{
is[i*pri[j]]=1;
if(i%pri[j])
f[i*pri[j]]=Mul(f[i],f[pri[j]]);
else
{
f[i*pri[j]]=Mul(f[i],pri[j]);
break;
}
}
//f[i]=Plus(f[i-1],f[i]);注意不能顺便加，因为后面可能还要用
}
for(int i=1;i<=10000000;++i)
f[i]=Plus(f[i-1],f[i]);
int T,n,m;
scanf("%d",&T);
while(T--)
{
scanf("%d%d",&n,&m);
if(n>m)
{
int t=n;
n=m;
m=t;
}
int ans=0;
for(int i=1;i<=n;++i)
{
int N=n/i,M=m/i;
int nxt=Min(n/N,m/M);
ans=Plus(ans,Mul(Mul(Mul(N,N+1),Mul(M,M+1)),Plus(f[nxt],p-f[i-1])));
i=nxt;
}
printf("%d\n",Mul(ans,75000007));
}
return 0;
}

Subscribe

/* */