题目链接

题解

此题太优美了

我们令\(\frac{x}{y}\)为最简分数，则\(x \perp y\)即，\(gcd(x,y) = 1\)

先不管\(k\)进制，我们知道\(10\)进制下如果\(\frac{x}{y}\)是纯循环的，只要\(2 \perp y\)且\(5 \perp y\)

可以猜想在\(k\)进制下同样成立

证明：

若\(\frac{x}{y}\)为纯循环小数，设其循环节长度为\(l\)，那么一定满足

\[\{ \frac{xk^{l}}{y} \} = \{ \frac{x}{y}\}\]

其中\(\{x\}\)指小数部分

可以写成

\[xk^{l}- \lfloor \frac{xk^{l}}{y} \rfloor * y= x - \lfloor \frac{x}{y} \rfloor * y\]

可以看出就是同余的形式

\[xk^{l} \equiv x \pmod y\]

由于\(x \perp y\)

\[k^{l} \equiv 1 \pmod y\]

要使存在\(l\)，使得式子成立，那么一定\(k \perp y\)

所以我们有

\[ \begin{aligned} ans &= \sum\limits_{i = 1}^{n} \sum\limits_{j = 1}^{m} [i \perp j] [j \perp k] \\ &= \sum\limits_{j = 1}^{m} [j \perp k] \sum\limits_{i = 1}^{n} [(i,j) == 1] \\ &= \sum\limits_{j = 1}^{m} [j \perp k] \sum\limits_{i = 1}^{n} \epsilon((i,j)) \\ &= \sum\limits_{j = 1}^{m} [j \perp k] \sum\limits_{i = 1}^{n} \sum\limits_{d|(i,j)} \mu(d) \\ &= \sum\limits_{d = 1}^{n} \mu(d) \sum\limits_{d|i}^{n} \sum\limits_{d|j}^{m} [j \perp k] \\ &= \sum\limits_{d = 1}^{n} [d \perp k] \mu(d) \lfloor \frac{n}{d} \rfloor \sum\limits_{j}^{\lfloor \frac{m}{d} \rfloor} [j \perp k] \\ \end{aligned} \]

我们令

\[f(n) = \sum\limits_{i}^{n} [i \perp k]\]

根据\(gcd(i + k,k) = gcd(i,k)\)，我们有

\[f(n) = \lfloor \frac{n}{k} \rfloor f(k) + f(n \mod k)\]

所以我们只需要\(O(klogk)\)暴力计算\(f(1....k)\)就可以\(O(1)\)计算后面的式子了

现在考虑前面的

\[\sum\limits_{d = 1}^{n} [d \perp k] \mu(d)\]

为了使能整除分块，我们必须算出其前缀和

令

\[g(n,k) = \sum\limits_{i = 1}^{n} [i \perp k] \mu(d)\]

用类似上面同样的方法：

\[ \begin{aligned} g(n,k) &= \sum\limits_{i = 1}^{n} [i \perp k] \mu(i) \\ &= \sum\limits_{i = 1}^{n} \mu(i) \sum\limits_{d|i,d|k} \mu(d) \\ &= \sum\limits_{d | k} \mu(d) \sum\limits_{d|i} \mu(i) \\ &= \sum\limits_{d | k} \mu(d) \sum\limits_{i = 1}^{\lfloor \frac{n}{d} \rfloor} \mu(id) \\ &= \sum\limits_{d | k} \mu(d) \sum\limits_{i = 1}^{\lfloor \frac{n}{d} \rfloor} [i \perp d]\mu(i) * \mu(d) \\ &= \sum\limits_{d | k} \mu(d)^2 \sum\limits_{i = 1}^{\lfloor \frac{n}{d} \rfloor} [i \perp d]\mu(i) \\ &= \sum\limits_{d | k} \mu(d)^2 g(\lfloor \frac{n}{d} \rfloor,d) \\ \end{aligned} \]

就可以递归求解

当\(n = 0\)时，\(g(0,k) = 0\)

当\(k = 1\)时，\(g(n,1) = \sum\limits_{i = 1}^{n} \mu(i)\)，上杜教筛即可

因为\(\lfloor \frac{n}{d} \rfloor\)只有\(\sqrt{n}\)种取值，\(d\)只能取\(k\)的因子，记其数量为\(p\)

那么求\(g(n,k)\)总的复杂度为\(O(p\sqrt{n} + n^{\frac{2}{3}})\)

于是乎我们就解决这道题了

总复杂度\(O(p\sqrt{n} + n^{\frac{2}{3}} + \sqrt{n} + klogk)\)

#include
    
     #include
     
      #include
      
       #include