Noi2016D1T3 循环之美

Noi2016D1T3 循环之美

这题真神 啊。

一个数是不是循环小数只和他的分母有关,显然 当分母和k互质的时候是纯循环小数

所以我们的得到了最基本的答案的式子:\sum_{i=1}^{n}\sum_{j=1}^{m}{[(i,j)=1][(j,k)=1]} .

然后直接上莫比乌斯反演:\sum_{i=1}^{n}\sum_{j=1}^{m}[(j,k)=1]\sum_{d|(i,j)}\mu(d)

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

g(x)=\sum_{j=1}^{x}[(j,k)=1], 由于(j,k)=(j+k,k),那么可以将1xk个分成一段,有g(x)=\lfloor\frac{x}{k}\rfloor g(k)+g(x \bmod k)

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

通过预处理k以内的g值,就可以O(1)得到每个g了。

f(n,k)=\sum_{d=1}^n[(d,k)=1]\mu(d),设k=p^x q,其中p为质数且(p,q)=1,有

f(n,k)=f(n,q)-\sum_{d=1}^{\lfloor\frac{n}{p}\rfloor}[(dp,q)=1]\mu(dp)
由于(p,q)=1[f(n,k)=f(n,q)-\sum_{d=1}^{\lfloor\frac{n}{p}\rfloor}[(d,q)=1]\mu(dp)

(d,q)!=1\mu(dp)=0,又p为质数,所以又可以写成\begin{aligned}f(n,k)=&f(n,q)+\sum_{d=1}^{\lfloor\frac{n}{p}\rfloor}[(d,k)=1]\mu(d)\\=&f(n,q)+f(\lfloor\frac{n}{p}\rfloor,k)\end{aligned}

边界f(n,1)=\sum_{d=1}^{n}\mu(d)

那么通过根号枚举\lfloor\frac{n}{d}\rfloor\lfloor\frac{m}{d}\rfloor,用杜教筛处理\mu的前缀和就可以在规定时间内解决了,复杂度O(\omega(k)\sqrt{n}+n^{\frac{2}{3}})

 

9 thoughts on “Noi2016D1T3 循环之美

zjq进行回复 取消回复

电子邮件地址不会被公开。 必填项已用*标注