P1587
[NOI2016] 循环之美
首先是这个小结论，满足什么条件这个小数才是纯循环的？
我们设循环节长度为 $z$，那么我们有如下结论：
$$
\dfrac {x k ^ z } { y } - \left\lfloor \dfrac { x k ^ z } { y } \right\rfloor = \dfrac { x } { y } - \left\lfloor \dfrac { x } { y } \right\rfloor
$$
意思就是，这两个数的小数部分是相同的。
换句话说，上面的式子实际上使 $x k ^ z $ 满足了：
$$ x k ^ z \equiv x \pmod { y }$$
首先题目要求我们求的是最简分数，所以说必然有 $x \perp y$，因此我们这个式子可以两边同时乘上 $x ^ { - 1 }$。
好，现在我们就有了条件：
$$ k ^ z \equiv 1 \pmod {y}$$
我来 yy 一种奇怪的解释。
上式说明，我们必然存在一个 $x$ 使得：
$$k ^ z x \equiv 1 \pmod { y }$$
根据同余方程的那一套理论，我们可以知道当且仅当 $k ^ z \perp y$ 的时候方程有解。
因此必然会有 $y \perp k$，实际上这就是纯循环的充要条件。
现在我们找到两个条件，不难发现我们答案实际上就是：
$$
\begin{aligned}
& \sum _ { x = 1 } ^ { n } \sum _{ y =1 } ^ { m } [ x \perp y ] [ y \perp k ]
\\
= & \sum _ { x = 1 } ^ { n } \sum _{ y =1 } ^ { m } \sum _{ d \mid y , d \mid x} \mu (d) [ y \perp k ]
\\
= & \sum _ { d = 1 } ^ { \min \{ n , m \} } \mu ( d ) \sum _{ x = 1 } ^ { \lfloor n / d \rfloor} \sum _ { y = 1 } ^ { \lfloor m / d \rfloor} [ yd \perp k ]
\\
= & \sum _ { d = 1 } ^ { \min \{ n , m \} } \mu ( d ) [ d \perp k ] \left \lfloor \dfrac { n } { d } \right \rfloor \sum _ { y = 1 } ^ { \lfloor m / d \rfloor} [ y \perp k ]
\end{aligned}
$$
现在这个东西就可以数论分块 $d$ 这一维，然后尝试快速处理后面的 $y$ 的求和。
尝试抽象出两个函数：
$$g ( n , k ) = \sum _ { d = 1 } ^ { n } \mu ( d ) [ d \perp k ]$$
$$f ( n , k ) = \sum _ { d = 1 } ^ { n } [ d \perp k ]$$
我们发现 $ f ( n , 1 )$ 是易求的，而 $g ( n , 1 )$ 通过杜教筛也是易求的。
考虑类似 Min-25 筛的方法，通过素数来递归求值。
发现我们的 $k$ 的平方因子在互质条件中都是多余的，因此我们把 $k$ 化简素数幂都为 1 的形式。
这样我们考虑一个素数 $p \mid k$，先从 $f$ 开始：
$$
\begin{aligned}
f ( n , k ) = & \sum _ {d = 1 } ^ { n } [ d \mid k ]
\\
= & \sum _ { d = 1 } ^ { n } [ d \mid ( k / p )] - \sum _ { d = 1 } ^ { n } [ d \mid (k/p) ] [ p \mid d]
\\
= & f ( n , k/p) - \sum _ {d = 1 } ^ {\lfloor n/p \rfloor} [ dp \mid ( k / p ) ]
\\
= & f ( n , k/p) - \sum _ {d = 1 } ^ {\lfloor n/p \rfloor} [ d \mid ( k / p ) ]
\\
= & f ( n , k / p ) - f ( \lfloor n / p \rfloor , k / p )
\end{aligned}
$$
然后再来看 $g$ 的推导：
$$
\begin{aligned}
g ( n , k ) = & \sum _ { d = 1 } ^ { n } \mu ( d ) [ d \perp k]
\\
= & \sum _ { d = 1 } ^ { n } \mu ( d ) [ d \perp ( k / p ) ] - \sum _ { d = 1 } ^ { n } \mu ( d ) [ d \perp ( k / p ) ] [ p \perp d ]
\\
= & g ( n , k / p ) - \sum _ { d = 1 } ^ { \lfloor n / p \rfloor} \mu ( d p ) [ d p \perp ( k / p ) ]
\\
= & g ( n , k / p ) - \mu ( p ) \sum _ { d = 1 } ^ { \lfloor n / p \rfloor} \mu ( d ) [ d \perp p] [ d \perp ( k / p ) ]
\\
= & g ( n , k / p ) + \sum _ { d = 1 } ^ { \lfloor n / p \rfloor} \mu ( d ) [ d \perp k ]
\\
= & g (n , k / p ) + g ( \lfloor n / p \rfloor , k)
\end{aligned}
$$
然后这玩意就可以递归计算了。
关于这个复杂度。
每次递推是 $ O( 1 ) $ 的（虽然我写的只是近似 $ O( 1 ) $）。
考虑到 $f,g$ 的第一位实际上是被数论分块过的，所以说仅仅只有 $O(\sqrt{n})$ 个起始递推。
然后这个递推的层数是 $k$ 的素因子个数，其级别为 $O(\log k / \log \log k)$。
因此递推的复杂度是 $ O(\sqrt {n} \log k / \log \log k)$ 的。
然后这个杜教筛的总复杂度是 $ O( n ^ {2 / 3 })$ 的，因为上界没变。。。
代码：
1 |
|