bzoj2154和luogu3768

bzoj2154

题意

$$\sum_{i=1}^n\sum_{j=1}^mlcm(i,j)\ \ n,m \leq 10^7$$

题解

$$\sum_{i=1}^n\sum_{j=1}^mlcm(i,j)=\sum_{i=1}^n\sum_{j=1}^m{ij\over gcd(i,j)}$$

$$F(x, y) = \sum_{i=1}^{x} \sum_{j=1}^{y} ij[gcd(i,j)=1]$$

$$原式=\sum_{d=1}^{n} \frac{d^2 F( \frac{n}{d} , \frac{m}{d} )}{d} = \sum_{d=1}^{n} d F(\frac{n}{d} , \frac{m}{d} )$$

$$F(x, y)= \sum_{i=1}^{x} \sum_{j=1}^{y} ij[gcd(i,j)=1]$$

$$= \sum_{i=1}^{x} \sum_{j=1}^{y} ij \sum_{d|(i,j)} \mu (d)$$

$$= \sum_{d=1}^{x} \mu (d) \sum_{d|i}^{x} i \sum_{d|j}^{y} j$$

$$= \sum_{d=1}^{x} \mu (d) d^2 \sum_{i=1}^{ \frac{x}{d}} i \sum_{j=1}^{\frac{y}{d}} j$$

$$= \sum_{d=1}^{x} \mu (d) d^2 \frac{\frac{x}{d} ( \frac{x}{d}+1)}{2} \frac{\frac{y}{d} (\frac{y}{d} +1)}{2}$$

$$原式=\sum_{d=1}^{n} d F( \frac{n}{d} , \frac{m}{d} )$$

$$\large = \sum_{d=1}^{n} d \sum_{i=1}^{ \frac{n}{d} } \mu (i) i^2 \frac{ \frac{ \frac{n}{d} }{i} ( \frac{ \frac{n}{d} }{i} +1)}{2} \frac{ \frac{ \frac{m}{d} }{i} ( \frac{ \frac{m}{d} }{i} +1)}{2}$$

$$= \sum_{d=1}^{n} d \sum_{i=1}^{ \frac{n}{d} } \mu (i) i^2 \frac{ \frac{n}{di} ( \frac{n}{di} +1)}{2} \frac{ \frac{m}{di} ( \frac{m}{di} +1)}{2}$$

$$\sum_{d=1}^{n} d \sum_{i=1}^{ \frac{n}{d} } \mu (i) i^2 \frac{ \frac{n}{di} ( \frac{n}{di} +1)}{2} \frac{ \frac{m}{di} ( \frac{m}{di} +1)}{2}$$

$$= \sum_{T=1}^{n} \frac{ \frac{n}{T} ( \frac{n}{T} +1)}{2} \frac{ \frac{m}{T} ( \frac{m}{T} +1)}{2} \sum_{i|T} \frac{T}{i} \mu (i) i^2$$

$$= \sum_{T=1}^{n} \frac{ \frac{n}{T} ( \frac{n}{T} +1)}{2} \frac{ \frac{m}{T} ( \frac{m}{T} +1)}{2} T \sum_{i|T} \mu (i) i$$

$i$取的数的因子中不包含新加入的$p$时，同上，答案是$f(k)$

$$\sum_{i|T} \mu(i) i$$

$$= \sum_{ap|kp} \mu (ap) ap$$

$$= p \sum_{a|k} \mu (a) \mu(p) a$$

$$= -p \sum_{a|k} \mu(a) a$$

$$= -p f(k)$$

luogu3768

题意

$$\sum_{i=1}^n\sum_{j=1}^nijgcd(i,j) \bmod p$$

题解

$$F(x, y) = \sum_{i=1}^{x} \sum_{j=1}^{y} ij[gcd(i,j)=1]$$

$$原式=\sum_{d=1}^{n} d^3 F( \frac{n}{d} , \frac{n}{d} )$$

$$F(x, y)= \sum_{i=1}^{x} \sum_{j=1}^{y} ij[gcd(i,j)=1]$$

$$= \sum_{i=1}^{x} \sum_{j=1}^{y} ij \sum_{d|(i,j)} \mu (d)$$

$$= \sum_{d=1}^{x} \mu (d) \sum_{d|i}^{x} i \sum_{d|j}^{y} j$$

$$= \sum_{d=1}^{x} \mu (d) d^2 \sum_{i=1}^{ \frac{x}{d}} i \sum_{j=1}^{\frac{y}{d}} j$$

$$= \sum_{d=1}^{x} \mu (d) d^2 \frac{\frac{x}{d} ( \frac{x}{d}+1)}{2} \frac{\frac{y}{d} (\frac{y}{d} +1)}{2}$$

$$原式=\sum_{d=1}^{n} d^3 F( \frac{n}{d} , \frac{n}{d} )$$

$$\large = \sum_{d=1}^{n} d^3 \sum_{i=1}^{ \frac{n}{d} } \mu (i) i^2 (\frac{ \frac{ \frac{n}{d} }{i} ( \frac{ \frac{n}{d} }{i} +1)}{2} )^@$$

$$= \sum_{d=1}^{n} d^3 \sum_{i=1}^{ \frac{n}{d} } \mu (i) i^2( \frac{ \frac{n}{di} ( \frac{n}{di} +1)}{2})^2$$

$$= \sum_{T=1}^{n} (\frac{ \frac{n}{T} ( \frac{n}{T} +1)}{2})^2 \sum_{i|T} (\frac{T}{i})^3 \mu (i) i^2$$

$$= \sum_{T=1}^{n} (\frac{ \frac{n}{T} ( \frac{n}{T} +1)}{2})^2 T^2 \sum_{i|T} \mu (i) \frac{T}{i}$$

$$= \sum_{T=1}^{n} (\frac{ \frac{n}{T} ( \frac{n}{T} +1)}{2})^2 T^2 \sum_{i|T} \mu (\frac{T}{i}) i$$

$$f(x)=x^2\sum_{i|x}\mu({x \over i})i$$

$$g(x)=\sum_{i|x}\mu({x \over i})i =\sum_{i|x}\mu(i){x \over i}$$

$$g(kp)=\sum_{i|kp} \mu({kp \over i})i=\sum_{i|kp} \mu(i){kp \over i}$$

$$=\mu({kp \over ap})ap=\mu({k \over a})ap$$

$i$取的数的因子中不包含新加入的$p$时，同上，答案是$g(k)$

$$\sum_{i|x} \mu({x \over i})i$$

$$= \sum_{ap|kp} \mu(ap){kp \over ap}$$

$$= \sum_{a|k} \mu (a) \mu(p) {k \over a}$$

$$= -\sum_{a|k} \mu(a) a$$

$$= – g(k)$$

$$g(x)=(h*\mu)(x)$$

$$h*\mu*1=h*(\mu*1)=h*\epsilon=h$$

$$(f*c)(x)$$

$$=\sum_{d|x}f(x)c({x\over d})$$

$$=\sum_{d|x}d^2\phi{x^2 \over d^2}$$

$$=x^2\sum_{d|x}\phi(x)=x^3$$

$$c(1)s(n)=\sum_{i=1}^n(f*c)(i)-\sum_{i=2}^nc(i)s({n \over i})$$

$$s(n)=\sum_{i=1}^ni^3-\sum_{i=2}^ni^2s({n\over i})$$