推公式[NOI2016]循环之美

· · 个人记录

题面

ans=\sum_{y=1}^m[(y, k) == 1]\sum_{x=1}^n[(x, y) == 1] =\sum_{y=1}^m[(y, k) == 1]\sum_{x=1}^ne((x, y)) =\sum_{y=1}^m[(y, k) == 1]\sum_{x=1}^n(\mu*I)((x, y)) =\sum_{y=1}^m[(y, k) == 1]\sum_{x=1}^n\sum_{d|(x,y)}\mu(d) =\sum_{d=1}^{n}\mu(d)\sum_{d|x}\sum_{d|y}[(y, k) == 1] =\sum_{d=1}^n[(d, k) == 1]\mu(d)\lfloor\frac{n}{d}\rfloor\sum_{y=1}^{\lfloor\frac{m}{d}\rfloor}[(y, k) == 1]

令f(n)=\sum_{i=1}^n[(i, k) == 1] 由(i+k, k)=(i, k)得

f(n)=\lfloor\frac{n}{k}\rfloor f(k)+f(n$ $mod$ $k)

所以可以预处理出f(n)的值

ans=\sum_{d=1}^n[(d, k) == 1]\mu(d)\lfloor\frac{n}{d}\rfloor f(\lfloor\frac{m}{d}\rfloor)

令g(n,k)=\sum_{i=1}^n[(i,k) == 1]\mu(i) 则同理g(n, k)=\sum_{i=1}^n\mu(i)\sum_{d|i, d|k}\mu(d)

=\sum_{d|k}\mu(d)\sum_{d|i}\mu(i) =\sum_{d|k}\mu(d)\sum_{i=1}^{\lfloor\frac{n}{d}\rfloor}\mu(id) =\sum_{d|k}\mu(d)\sum_{i=1}^{\lfloor\frac{n}{d}\rfloor}[(i,d) == 1]\mu(i)\mu(d) =\sum_{d|k}\mu(d)^2\sum_{i=1}^{\lfloor\frac{n}{d}\rfloor}[(i,d) == 1]\mu(i) =\sum_{d|k}\mu(d)^2g(\lfloor\frac{n}{d}\rfloor, d)

所以g(n, k)可以递归求解

ans=\sum_{d=1}^n[(d, k) == 1]\mu(d)\lfloor\frac{n}{d}\rfloor f(\lfloor\frac{m}{d}\rfloor)