是上文里 2021/4/24 里的记录,由于都是关于积性函数的三道杂题,所以单独放出来。

约定:用 $(i,j)$ 表示 $\gcd(i,j)$,用 $[i,j]$ 表示 $\text{lcm}(i,j)$,$[P]$ 在事件 $P$ 为真时等于 $1$,否则等于 $0$。

51nod1584 加权约数和

求 $\sum_{i=1}^n\sum_{j=1}^n max(i,j)*\sigma(ij)$,$T$ 组数据。

$T\leq 50000,n\leq 10^6$。

首先令 $A=\sum_{i=1}^n\sum_{j=1}^i i*\sigma(ij),B=\sum_{i=1}^n i*\sigma(i^2)$,那么有 $ans=2A-B$。

$B$ 随便搞一搞就好了,主要看 $A$。

$$ \begin{aligned} f(i)&=i·\sum_{j=1}^i \sigma(ij)\\ &=i\sum_{j=1}^i\sum_{p|i}\sum_{q|j}[(p,q)=1]p·\frac{j}{q}\\ &=i\sum_{j=1}^i\sum_{d|i,d|j}\mu(d)\sum_{d|p,p|i}p\sum_{d|q,q|j}\frac{j}{q}\\ &=i\sum_{j=1}^i\sum_{d|i,d|j}\mu(d)·d·\sigma(\frac{i}{d})\sigma(\frac{j}{d})\quad\color{red}{[1]}\\ &=i\sum_{d|i}\mu(d)·d·\sigma(\frac{i}{d})\sum_{j=1}^{\frac{i}{d}}\sigma(j)\\ \end{aligned} $$

$$ \begin{aligned} \color{red}{[1]}:&\sum_{d|p,p|i}p=\sum_{p|\frac{i}{d}}p·d=d·\sigma(\frac{i}{d})\\ &\sum_{d|q,q|j}\frac{j}{q}=\sum_{q|\frac{j}{d}}\frac{\frac{j}{d}}{q}=\sum_{q|\frac{j}{d}}q=\sigma(\frac{j}{d}) \end{aligned} $$

$$ A=\sum_{i=1}^nf(i) $$

于是这道题就做完了。

code

bzoj3561 DZY loves Math VI

求 $\sum_{i=1}^n\sum_{j=1}^m \text{lcm}(i,j)^{\gcd(i,j)}$,$n,m\leq 5*10^5$。

老套路题了,挺好做的。令 $n≥m$。

$$ \begin{aligned} ans&=\sum_d\sum_{i=1}^{\lfloor\frac{n}{d}\rfloor}\sum_{j=1}^{\lfloor\frac{m}{d}\rfloor}[(i,j)=1]i^dj^dd^d\\ &=\sum_dd^d\sum_{i=1}^{\lfloor\frac{n}{d}\rfloor}\sum_{j=1}^{\lfloor\frac{m}{d}\rfloor}\sum_{g|(i,j)}\mu(g)i^dj^d{g^{d}}^2\\ &=\sum_dd^d\sum_{g=1}^{\lfloor\frac{n}{d}\rfloor}\mu(g){g^d}^2\sum_{i=1}^{\lfloor\frac{n}{dg}\rfloor}i^d\sum_{j=1}^{\lfloor\frac{m}{dg}\rfloor}j^d \end{aligned} $$

于是你惊奇地推到这一步之后感觉推不动了,但是观察柿子发现暴力算的时间复杂度已经只有 $\mathcal O(n\log p+n\ln n)$ 了。

$n\log p$ 是算 $d^d$ 的,$n\ln n$ 是对于每个 $d$ ,暴力地 $\mathcal O(\lfloor\frac{n}{d}\rfloor)$ 算 $i^d$ 及其前缀和的。然后就过了。

code

CodeChef LCM-Adding Least Common Multiples

求 $\sum_{i=1}^n\sum_{j=1}^m\mu^2(\gcd(i,j))[i,j]$,$T$ 组数据,$n,m\leq 4*10^6,T\leq200$,时限 $0.2s$。

很朴素地展开:

$$ \begin{aligned} ans&=\sum_{d=1}^n\mu^2(d)·d\sum_{i=1}^{\lfloor\frac{n}{d}\rfloor}\sum_{j=1}^{\lfloor\frac{m}{d}\rfloor}[(i,j)=1]·ij\\ &=\sum_{d=1}^n\mu^2(d)·d\sum_{g=1}^{\lfloor\frac{n}{d}\rfloor}\mu(g)·g^2· S(\lfloor\frac{n}{dg}\rfloor)·S(\lfloor\frac{m}{dg}\rfloor) \end{aligned} $$

其中 $S(n)=\sum_{i=1}^n i=\frac{n(n+1)}{2}$。

至此,已经可以两次数论分块做到 $\mathcal O(Tn^{\frac{3}{4}})$ 了,但是常数大到离谱,时间复杂度也难以通过(指本地需要跑 $2s$)。

于是继续考虑改为枚举 $T=dg$。

$$ \begin{aligned} ans&=\sum_{T=1}^n\sum_{d|T}\mu^2(d)\mu(\frac{T}{d})·\frac{T}{d}·T·S(\lfloor\frac{n}{T}\rfloor)·S(\lfloor\frac{m}{T}\rfloor)\\ &=\sum_{T=1}^nT·S(\lfloor\frac{n}{T}\rfloor)·S(\lfloor\frac{m}{T}\rfloor)\sum_{d|T}\mu^2(d)\mu(\frac{T}{d})·\frac{T}{d} \end{aligned} $$

考虑设 $f(n)=\sum_{d|n}\mu^2(d)\mu(\frac{n}{d})·\frac{n}{d}$,这东西由 $\mu^2,\mu,\text{id}$ 组成,容易证明是个积性函数。

于是考虑 $f(p)=1-p,f(p^2)=-p,f(p^3)=0$ 之后就可以暴力线筛出来了。

$$ ans=\sum_{T=1}^nf(T)·S(\lfloor\frac{n}{T}\rfloor)·S(\lfloor\frac{m}{T}\rfloor) $$

线性筛出 $f$ 之后算个前缀和就可以数论分块了,时间复杂度 $\mathcal O(T\sqrt{n})$,可以轻松通过。

code

最后修改:2021 年 04 月 25 日 07 : 46 PM