题如其名，这道题十分优美

首先，如果$\dfrac xy$在$k$进制下是循环节长度为$l$的纯循环小数，那么$\dfrac xy$和$\dfrac{xk^l}y$的小数部分是一样的，也就是说$x\equiv xk^l(\bmod y)$，即$k^l\equiv1(\bmod y)$，这时就有$(k,y)=1$，显然以上每一步都是充分必要的

所以我们要求$\sum\limits_{i=1}^n\sum\limits_{j=1}^m[(i,j)=1][(j,k)=1]$，先推一下式子

$\begin{aligned}\sum\limits_{i=1}^n\sum\limits_{j=1}^m[(i,j)=1][(j,k)=1]&=\sum\limits_{j=1}^m[(j,k)=1]\sum\limits_{i=1}^n\sum\limits_{\substack{d|i\\d|j}}\mu(d)\\&=\sum\limits_{d=1}^{\min(n,m)}\mu(d)\left\lfloor\frac nd\right\rfloor\sum\limits_{j=1}^{\left\lfloor\frac md\right\rfloor}[(jd,k)=1]\\&=\sum\limits_{d=1}^{\min(n,m)}\mu(d)\left\lfloor\frac nd\right\rfloor[(d,k)=1]\sum\limits_{j=1}^{\left\lfloor\frac md\right\rfloor}[(j,k)=1]\end{aligned}$

现在我们要求两个东西：$f(n)=\sum\limits_{i=1}^n[(i,k)=1]$和$g(n,k)=\sum\limits_{i=1}^n\mu(i)[(i,k)=1]$

$f(n)=\left\lfloor\frac nk\right\rfloor f(k)+f(n\%k)$，预处理$f(1\cdots k)$即可

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

中间多出来的中括号不是无中生有，因为如果$(i,d)\ne1$那么$\mu(id)=0$，这一步是比较妙的地方

于是我们可以递归求值，递归到$k=1$时直接杜教筛，这里的时间复杂度是$O(n^{\frac23})$，观察递归式，我们可以只分析$d$的取值，有$O(\sigma_0(k))$个不同的$d$，每次转移耗费时间为$O(\sigma_0(d))$，加上最外层的根号分段，总时间复杂度为$O\left(n^{\frac23}+\sigma_0^2(k)\sqrt n\right)$，当然这个上界很松，所以跑得还是挺快的

The beautiful math.

#include
     
      #include
      
       #include