求 \(k\) 进制下可以表示为纯循环小数（认为整数也是）的既约分数 \(\dfrac{i}{j}\)，且 \(1\leqslant i\leqslant n\)，\(1\leqslant j\leqslant m\) 的个数。\(n,m\leqslant 10^9\)，\(k\leqslant 2000\)。
经过尝试可以发现，既约分数 \(\dfrac{i}{j}\) 在 \(k\) 进制下是纯循环的当且仅当 \(\gcd(j,k)=1\)（证明可以见其它题解）。
所以，我们只需要求 \[ \sum\limits_{i=1}^n\sum\limits_{j=1}^m[\gcd(i,j)=1][\gcd(j,k)=1] \] 因为要既约分数，所以要保证 \(\gcd(i,j)=1\)。
因为两个 \(\gcd\) 都与 \(j\) 有关，我们考虑把 \(j\) 提到外面 \[ ans=\sum\limits_{j=1}^m[\gcd(j,k)=1]\sum\limits_{i=1}^n[\gcd(i,j)=1] \] 然后我们对后面来一次莫比乌斯反演 \[ \begin{aligned} ans&=\sum\limits_{j=1}^m[\gcd(j,k)=1]\sum\limits_{i=1}^n\sum\limits_{d\mid i,d\mid j}\mu(d)\\ &=\sum\limits_{j=1}^m[\gcd(j,k)=1]\sum\limits_{d\mid j}\lfloor\frac{n}{d}\rfloor\mu(d) \end{aligned} \] 然后我们把 \(d\) 提到前面去 \[ ans=\sum\limits_{d=1}^n\lfloor\frac{n}{d}\rfloor\mu(d)\sum\limits_{d\mid j,j\leqslant m}[\gcd(j,k)=1] \] 我们发现，\(j\) 可以表示为 \(xd\)，那么 \(\gcd(j,k)=1\) 等价于 \(\gcd(x,k)=1\) 且 \(\gcd(d,k)=1\) ，于是我们有 \[ ans=\sum\limits_{d=1}^n\lfloor\frac{n}{d}\rfloor\mu(d)[\gcd(d,k)=1]\sum\limits_{x=1}^{\lfloor\frac{m}{d}\rfloor}[\gcd(x,k)=1] \] 然后我们观察第二个求和号，如果我们设 \(f(z)=\sum\limits_{i=1}^z[\gcd(i,k)=1]\)，那么后面的就是 $ f()$。
我们考虑是否能够快速计算 \(f\)，根据辗转相除（减）法的原理，我们有 \(\gcd(x,k)=\gcd(x+k,k)\)，所以我们有 \[ f(z)=\lfloor \frac{z}{k}\rfloor f(k)+f(z\bmod k) \] 即我们按照每个数模 \(k\) 的余数将其分为若干等价类。这样我们只需要预处理 \(f(1)\dots f(k)\) 就可以在 \(O(1)\) 时间内计算 \(f(z)\)。
那么有 \[ ans=\sum\limits_{d=1}^n\lfloor\frac{n}{d}\rfloor f(\lfloor\frac{m}{d}\rfloor)\mu(d)[\gcd(d,k)=1] \] 我们发现，如果我们可以快速计算 \(\mu(d)[\gcd(d,k)=1]\) 的前缀和，我们就可以通过整除分块计算答案，那么问题就转化为了快速计算 \(\mu(d)[\gcd(d,k)=1]\) 的前缀和。
我们设 \(g(z)=\sum\limits_{d=1}^z\mu(d)[\gcd(d,k)=1]\)，那么我们再来一次莫比乌斯反演： \[ \begin{aligned} g(z)&=\sum\limits_{d=1}^z\mu(d)\sum\limits_{t\mid d,t\mid k}\mu(t)\\ &=\sum\limits_{t\mid k}\mu(t)\sum\limits_{t\mid d,d\leqslant z}\mu(d)\\ &=\sum\limits_{t\mid k}\mu(t)\sum\limits_{d=1}^{\lfloor\frac{z}{t}\rfloor}\mu(dt)\\ \end{aligned} \] 我们发现，如果 \(\gcd(d,t)\not= 1\)，那么 \(dt\) 一定含有平方因子（\(\gcd(d,t)^2\)），所以这时 \(\mu(dt)=0\)，由于我们只在乎和，所以我们可以只对 \(\mu(dt)\not=0\)，即 \(\gcd(d,t)=1\) 的情况计算。那么有： \[ g(z)=\sum\limits_{t\mid k}\mu(t)\sum\limits_{d=1}^{\lfloor\frac{z}{t}\rfloor}\mu(dt)[\gcd(d,t)=1] \] 这样由于我们强制令 \(d,t\) 互质，我们就可以把 \(\mu(dt)\) 拆成 \(\mu(d)\mu(t)\)： \[ \begin{aligned} g(z)&=\sum\limits_{t\mid k}\mu(t)\sum\limits_{d=1}^{\lfloor\frac{z}{t}\rfloor}\mu(d)\mu(t)[\gcd(d,t)=1]\\ &=\sum\limits_{t\mid k}\mu^2(t)\sum\limits_{d=1}^{\lfloor\frac{z}{t}\rfloor}\mu(d)[\gcd(d,t)=1] \end{aligned} \] 我们发现第二个求和号后面的东西和 \(g\) 很像，不过是 \([\gcd(d,t)=1]\) 而不是 \([\gcd(d,k)=1]\)，为此我们扩展一下 \(g\) 的定义，设 \(g(z,c)=\sum\limits_{i=1}^z\mu(i)[\gcd(i,c)=1]\)，那么 \[ g(z,c)=\sum\limits_{t\mid c}\mu^2(t)g(\lfloor\frac{z}{t}\rfloor,t) \] 边界条件为 \(c=1\)，此时就是莫比乌斯函数的前缀和，可以杜教筛求解。注意计算时要记忆化，复杂度据说是 \(O(n^{\frac{2}{3}}+\sigma_0(k)\sqrt n)\) 的，不会证。
代码：
1 |
|