【NOI2016】循环之美
问题描述
牛牛是一个热爱算法设计的高中生。在他设计的算法中，常常会使用带小数的数进行计算。牛牛认为，如果在 $k$ 进制下，一个数的小数部分是纯循环的，那么它就是美的。
现在，牛牛想知道：对于已知的十进制数 $n$ 和 $m$，在 $k$ 进制下，有多少个数值上互不相等的纯循环小数，可以用分数 $\frac x y$ 表示，其中 $1\le x\le n,1\le y\le m$，且 $x,y$ 是整数。
一个数是纯循环的，当且仅当其可以写成以下形式：
$$a.\dot{c_1} c_2 c_3 \ldots c_{p - 1} \dot{c_p}$$
其中，$a$ 是一个整数，$p\ge1$；对于 $1\le i\le p$，$c_i$ 是 $k$ 进制下的一位数字。例如，在十进制下，$0.45454545\dots=0.\dot{4}\dot{5}$ 是纯循环的，它可以用 $\frac 5 {11}$、$\frac{10}{22}$ 等分数表示；在十进制下，$0.1666666\dots=0.1\dot{6}$ 则不是纯循环的，它可以用 $\frac 1 6$ 等分数表示。
需要特别注意的是，我们认为一个整数是纯循环的，因为它的小数部分可以表示成 $0$ 的循环或是 $k-1$ 的循环；而一个小数部分非 $0$ 的有限小数不是纯循环的。
输入格式
输入文件只有一行，包含三个十进制数 $n,m,k$，意义如题所述。
输出格式
只输出一行一个整数，表示满足条件的美的数的个数。
样例输入 1
2 6 10
样例输出 1
4
样例输入 2
23333 666666 310
样例输出 2
5089564081
提示
对于所有的测试点，保证 $1\le n\le 10^9$，$1\le m\le 10^9$，$2\le k\le2000$。
首先考虑什么样的分数$\frac{x}{y}$满足他在$k$进制下是纯循环的，结论是满足$gcd(\frac{y}{gcd(x,y)},k)=1$的分数都是纯循环的。
证明的话，我们只考虑$gcd(x,y)=1$的情况，不为1的情况类似。那么$\frac{x}{y}$的小数部分只和$x\mod y$有关，那么如果他是纯循环的，假设循环节长度为$a$，一定有$x\equiv k^ax\mod y$，那么由于$(x,y)=1$，得到$k^a\equiv1\mod y$
上述方程有解当且仅当$gcd(k,y)=1$，这个可以用反证法轻易得证。
因此我们要求就是$\sum_{i=1}^{m}[gcd(i,k)=1]\sum_{j=1}^{n}[gcd(i,j)=1]$，注意到$[gcd(i,j)=1]=\sum_{d|gcd(i,j)}\mu(d)$，于是
$$
\begin{align}
Ans&=\sum_{i=1}^{m}[gcd(i,k)=1]\sum_{j=1}^{n}\sum_{d|gcd(i,j)}\mu(d)=\sum_{d=1}^{min(n,m)}\mu(d)\sum_{i=1}^{m}[gcd(i,k)=1]\sum_{j=1}^{n}[d|gcd(i,j)]\\
&=\sum_{d=1}^{min(n,m)}\mu(d)\sum_{i=1}^{\lfloor\frac{m}{d}\rfloor}[gcd(id,k)=1]\lfloor\frac{n}{d}\rfloor=\sum_{d=1}^{min(n,m)}\mu(d)[gcd(d,k)=1]\lfloor\frac{n}{d}\rfloor\sum_{i=1}^{\lfloor\frac{m}{d}\rfloor}[gcd(i,k)=1]
\end{align}
$$
我们显然想要分块处理后面的部分，因此考虑怎么求$\sum_{i=1}^{\lfloor\frac{m}{d}\rfloor}[gcd(i,k)=1]$，令$g(n)=\sum_{i=1}^{n}[gcd(i,k)=1]$
$$
g(n)=\sum_{i=1}^{n}[gcd(i,k)=1]=\sum_{i=1}^{n}\sum_{d|gcd(i,k)}\mu(d)=\sum_{d|k}\lfloor\frac{n}{d}\rfloor\mu(d)
$$
因此我们可以在$O(\sqrt{k})$的复杂度内求出$g(n)$，现在考虑如何求$f(n,k)=\sum_{i=1}^{n}\mu(i)[gcd(i,k)=1]$，那么
$$
\begin{align}
f(n,k)&=\sum_{i=1}^{n}\mu(i)\sum_{d|gcd(i,k)}\mu(d)=\sum_{d|k}\mu(d)\sum_{i=1}^{\lfloor\frac{n}{d}\rfloor}\mu(id)
\\&=\sum_{d|k}\mu^2(d)\sum_{i=1}^{\lfloor\frac{n}{d}\rfloor}\mu(i)[gcd(i,d)=1]=\sum_{d|k}\mu^2(d)f(\lfloor\frac{n}{d}\rfloor,d)
\end{align}
$$
那么递归处理就行了，求一次的复杂度大概是$O(\sigma_0^2(k)\sqrt{k})+n^{\frac{2}{3}}$，边界情况是当$k=1$的时候，直接用杜教筛求$\mu(i)$的前缀和就行了
还有另外一种更快的处理方法。令$k=p^tq$，$p$为质数
$$
\begin{align}
f(n,p^tq)&=\sum_{i=1}^{n}\mu(i)[gcd(i,p^tq)=1]=\sum_{i=1}^{n}\mu(i)[gcd(i,q)=1]-\sum_{i=1}^{\lfloor\frac{n}{p}\rfloor}\mu(ip)[gcd(i,pq=1)]\\
&=\sum_{i=1}^{n}\mu(i)[gcd(i,q)=1]+\sum_{i=1}^{\lfloor\frac{n}{p}\rfloor}\mu(i)[gcd(i,pq)=1]=f(n,q)+f(\lfloor\frac{n}{p}\rfloor,pq)
\end{align}
$$
然后同样递归处理就行了，复杂度由因数个数变成了质因数个数。同样边界的时候用杜教筛求就好了。当$n=0$时直接返回。
记得一定要记忆化$f(n,k)$
1 |
|