AC. 梦想

frank_c1

[NOI 2016] 循环之美

发布于2017年04月14日 | 暂无评论 | 771阅读 | 数论,杜教筛,莫比乌斯反演

题目描述

牛牛是一个热爱算法设计的高中生。在他设计的算法中,常常会使用带小数的数进行计算。牛牛认为,如果在k进制下,一个数的小数部分是纯循环的,那么它就是美的。

现在,牛牛想知道:对于已知的十进制数nm,在k进制下,有多少个数值上互不相等的纯循环小数,可以用分数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 \ge 1;对于1 \le i \le pc_ik进制下的一位数字。

例如,在十进制下,0.45454545 \ldots \ldots = 0.\dot{4}\dot{5}是纯循环的,它可以用\frac{5} {11}\frac{10} {22}等分数表示;在十进制下,0.1666666\ldots \ldots = 0.1\dot{6}则不是纯循环的,它可以用\frac{1} {6}等分数表示。

需要特别注意的是,我们认为一个整数是纯循环的,因为它的小数部分可以表示成0的循环或是k - 1的循环;而一个小数部分非0的有限小数不是纯循环的。

输入格式

输入文件只有一行,包含三个十进制数n,m,k,意义如题所述。

1 \le n,m \le 10 ^ 9, 2 \le k \le 2000

输出格式

只输出一行一个整数,表示满足条件的美的数的个数。

题目解析

(这篇东西好像是去年NOI后写的…… 发现没写完,赶快填一波坑TAT

小范围打表后发现题目要求这样一个东西

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

同步赛考场上我只有半个小时做这题,就直接用这个式子暴力算了一下,只有24分2333

先来大力展开一波

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

对于还含有k\gcd,如果进一步用莫比乌斯反演展开并不怎么有效果。

不妨先观察一下式子,我们把i\lfloor \frac{n} {i} \rfloor, \lfloor \frac{m} {i} \rfloor的取值分成O(\sqrt{n} + \sqrt{m})段。可以发现,主要矛盾是需要快速求出下列两个函数的值,而且函数的输入都是形如\lfloor \frac{n} {x} \rfloor\lfloor \frac{m} {x} \rfloor的值。

F(n) = \sum_{i=1} ^ {n} {[\gcd(i,k) = 1]}

S(n) = \sum_{i=1} ^ {n} {\mu(i) [\gcd(i, k) = 1]}

我们发现,如果去掉\gcd(i,k) = 1的限制,S(n)就是我们熟悉的莫比乌斯函数前缀和,而F(n)就是n

怎样的整数满足i满足\gcd(i,k) = 1呢?回顾定义,如果ik不含公共质因子,则\gcd(i,k) = 1。也就是说,我们要像筛法一样,把[1, n]中所有k的质因子的倍数的贡献全部筛去。

于是DP的思路就很显然了(好像在很多地方都见到过这东西耶

k = \prod_{i} {p_i ^ {c_i}}S_i(n)表示筛完前i个质因子后的结果,F_i(n)同理。边界

F_0(n) = n

S_0(n) = \sum_{i=1} ^ {n} {\mu(i)}

转移有

F_i(n) = F_{i-1}(n) - F_{i-1}(\lfloor \frac{n}{p_i} \rfloor)

S_i(n) = S_{i-1}(n) - \mu(p_i) S_i(\lfloor \frac{n}{p_i} \rfloor)

由于下标都是形如\lfloor \frac{n} {x} \rfloor\lfloor \frac{m} {x} \rfloor的,计算所有需要的值的复杂度就是O(\omega(k) \sqrt{n})的。\omega(k)k中不同质因子的个数。S_0需要杜教筛,复杂度O(n ^ {\frac{2}{3}})。总时间复杂度O(\omega(k) \sqrt{n} + n ^ \frac{2}{3})。还是不明白k2000的意义所在啊?

程序实现也是一个比较有意思的问题。按照我的学习过程,我有这么几种实现方法。一开始map直接上,写的是爽,复杂度和常数上天咯。后来把map换成hash,写的不爽,复杂度是对了,常数又上天了。后来呢,学会按\lfloor \frac{n} {i} \rfloor\sqrt{n}的大小关系分成两段存在两个数组里,写的还是递归,至少是比哈希好写,常数小了一点。这次呢,我终于悟到了如何把所有函数都非递归起来(表bs我沙茶~),常数果然小,只要两秒了2333