题解 P1447 【[NOI2010]能量采集】

· · 个人记录

题意：

要你求：

\sum_{i=1}^n\sum_{j=1}^m 2\gcd(i,j)-1

以下均设 n\leq m

提一下 \gcd :

2\sum_{i=1}^n\sum_{j=1}^m\gcd(i,j) - n\times m

考虑研究这个东西：

\sum_{i=1}^n\sum_{j=1}^m\gcd(i,j)

按照套路枚举 \gcd :

\sum_{i=1}^n\sum_{j=1}^m\sum_{d}gcd(i,j)[gcd(i,j)=d] \sum_{d=1}^n\sum_{i=1}^{\left\lfloor{\frac{n}{d}}\right\rfloor}\sum_{j=1}^{\left\lfloor{\frac{m}{d}}\right\rfloor}gcd(id,jd)[gcd(id,jd)=d] \sum_{d=1}^n\sum_{i=1}^{\left\lfloor{\frac{n}{d}}\right\rfloor}\sum_{j=1}^{\left\lfloor{\frac{m}{d}}\right\rfloor}d[gcd(i,j)=1] \sum_{d=1}^nd\sum_{i=1}^{\left\lfloor{\frac{n}{d}}\right\rfloor}\sum_{j=1}^{\left\lfloor{\frac{m}{d}}\right\rfloor}[gcd(i,j)=1]

有 \mu*1=\epsilon

\sum_{d=1}^nd\sum_{i=1}^{\left\lfloor{\frac{n}{d}}\right\rfloor}\sum_{j=1}^{\left\lfloor{\frac{m}{d}}\right\rfloor}\sum_{p|\gcd(i,j)}\mu(p) \sum_{d=1}^nd\sum_{i=1}^{\left\lfloor{\frac{n}{d}}\right\rfloor}\sum_{j=1}^{\left\lfloor{\frac{m}{d}}\right\rfloor}\sum_{p|i,j}\mu(p) \sum_{d=1}^n d \sum_{p=1}^{\left\lfloor{\frac{n}{d}}\right\rfloor}\sum_{i=1}^{\left\lfloor{\frac{n}{dp}}\right\rfloor}\sum_{j=1}^{\left\lfloor{\frac{m}{dp}}\right\rfloor}\mu(p) \sum_{d=1}^n d \sum_{p=1}^{\left\lfloor{\frac{n}{d}}\right\rfloor}\mu(p)\left\lfloor{\frac{n}{dp}}\right\rfloor \left\lfloor{\frac{m}{dp}}\right\rfloor

到这里可以 O(n\sqrt n) 搞了。

考虑优化：设 x=dp 有：

\sum_{d=1}^n d \sum_{d|x}\mu(\frac{x}{d})\left\lfloor{\frac{n}{x}}\right\rfloor \left\lfloor{\frac{m}{x}}\right\rfloor \sum_{x=1}^n \left\lfloor{\frac{n}{x}}\right\rfloor \left\lfloor{\frac{m}{x}}\right\rfloor\sum_{d|x}d \mu(\frac{x}{d})

设后面的式子等于 h

h = \mu * Id h*1=\mu*Id*1 h*1=\epsilon*Id=Id = 1*\varphi

所以 h=\varphi

于是原式等于

\sum_{x=1}^n \left\lfloor{\frac{n}{x}}\right\rfloor \left\lfloor{\frac{m}{x}}\right\rfloor\varphi(x)

直接搞可以 O(n) ，结合杜教筛可以 O(n^{2/3}) 搞。