【题解】[NOI2016] 循环之美

[NOI2016] 循环之美

给定 $x,y,k$。
求分数 $\dfrac{x}{y}$ 的个数满足:$1\le x\le n,1\le y\le m,\gcd(x,y)=1$,且在 $k$ 进制下 $\dfrac{x}{y}$ 是纯循环小数(或者整数)。
$1\le n\le 10^9,\ 1\le m\le 10^9,\ 1\le k\le 2\times 10^3$。

$\text{Solution:}$

$k$ 进制不是我们熟悉的东西,考虑转化为十进制下的等式。

在将小数化为分数的时候,我们经常使用乘一个数字的方法来解决。例如把 $0.\dot{6}$ 化为分数的时候,令其为 $x$,我们将其 $\times 10$,那么 $x\times 10=6.\dot{6}$,也就是 $10x-x=6$,于是 $x=\dfrac{2}{3}$。

考虑类似的方式,设 $l$ 为小数循环节长度(事实上可以是任意倍数),令 $\{x\}$ 表示 $x$ 的小数部分,那么:

$$ \Big\{\dfrac{x}{y}\Big\}=\Big\{\dfrac{xk^l}{y}\Big\} $$

这种形式也比较陌生,再转化一下:

$$ \dfrac{x}{y}-\left\lfloor\dfrac{x}{y}\right\rfloor=\dfrac{xk^l}{y}-\left\lfloor\dfrac{xk^l}{y}\right\rfloor $$

乘以 $y$ 可得:

$$ x-\left\lfloor\dfrac{x}{y}\right\rfloor\times y=xk^l-\left\lfloor\dfrac{xk^l}{y}\right\rfloor\times y $$

也就是:

$$ x\equiv xk^l \pmod y\rightarrow k^l\equiv 1\pmod y $$

我们知道只要 $\gcd(y,k)=1$,就必然存在一个 $l=c$ 使得上式成立,取 $c$ 与循环节长度的 $\text{lcm}$ 即可。

那么题目变为求解:

$$ f(n,m,k)=\sum_{i=1}^n\sum_{j=1}^m[\gcd(i,j)=1][\gcd(j,k)=1] $$

拆掉 $[\gcd(j,k)=1]$,推推柿子可以得到:

$$ \sum_{d|k} \mu(d)\sum_{i=1}^n\sum_{j=1}^{\lfloor\frac{m}{d}\rfloor} [\gcd(i,jd)=1] $$

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

$$ \sum_{d|k} \mu(d)f(\left\lfloor\dfrac{m}{d}\right\rfloor,n,d) $$

可以递归处理。

对于边界情况,发现 $k=1$ 的时候就是一个基础莫比乌斯反演,但是需要杜教筛。

时间复杂度 $\mathcal{O}(\log n\log m\sqrt{n}+n^{\frac{2}{3}})$。

本题首先需要推出一个经典的结论:$\dfrac{x}{y}$ 在 $k$ 进制下纯循环当且仅当 $\gcd(y,k)=1$。这个是可以通过纯循环小数的性质——也就是利用循环节长度来推出的。

接着的莫比乌斯反演看起来有几种不同的方向,但是如果选择拆掉 $[\gcd(j,k)=1]$,由于其中有一个常量 $k$,所以可能是一个较好的方式。同时本题的求解方法提供了一个思路——递归求解,也就是最后我们在推柿子之后,将柿子化为了与原问题类似,规模更小的问题,于是就只需要考虑边界情况了。

添加新评论