【BZOJ4652】【NOI2016】循环之美

首先一个分数是不是纯循环小数只跟它的分母有关,很显然。

那么可以打表/yy/瞎jb猜结论得知,当分母与\(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)\),那么可以将\(1\)到\(x\)每\(k\)个分成一段,有\(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{align}
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{align}$$

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

那么通过根号枚举\(\lfloor\frac{n}{d}\rfloor\)和\(\lfloor\frac{m}{d}\rfloor\),用杜教筛处理\(\mu\)的前缀和就可以解决了。

说点什么

3 评论 在 "【BZOJ4652】【NOI2016】循环之美"

提醒
排序:   最新 | 最旧 | 得票最多
成员

总感觉这篇博客似乎少了点什么

成员

少了什么……全了什么……

wpDiscuz