【题解】[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$，所以可能是一个较好的方式。同时本题的求解方法提供了一个思路——递归求解，也就是最后我们在推柿子之后，将柿子化为了与原问题类似，规模更小的问题，于是就只需要考虑边界情况了。