手玩发现，一个极简分数，如果其分母和进制的 \(\gcd\) 为 \(1\)，那么就符合题意。
那么就变成了求 \(\sum_{i=1}^n\sum_{j=1}^m[(j,k)=1][(i,j)=1]\)。
其实这个求和式的化简并不难，只是需要多发现式子之间的联系。
1. 展开 \([(i,j)=1]\)。
\[ \begin{aligned} &\sum_{i=1}^n\sum_{j=1}^m[(j,k)=1][(i,j)=1]\\ =&\sum_{t=1}^n\mu(t)\lfloor\frac{n}{t}\rfloor\sum_{j=1}^{\lfloor\frac{m}{t}\rfloor}[(tj,k)=1]\\ =&\sum_{t=1}^n\mu(t)\lfloor\frac{n}{t}\rfloor[(t,k)=1]\sum_{a|k}\mu(a)\lfloor\frac{m}{ta}\rfloor\\ =&\sum_{a|k}\mu(a)\sum_{t=1}^n\mu(t)\lfloor\frac{n}{t}\rfloor[(t,k)=1]\lfloor\frac{m}{ta}\rfloor \end{aligned} \]
后面显然可以整除分块。但是分块后需要求 \(\sum_{i=1}^n\mu(i)[(i,k)=1]\)。到在这里博主就不会了，因为这个式子看起来不可推。但是实际上设这个为 \(g(n,k)\)，稍加整理： \[ \begin{aligned} &\sum_{i=1}^n\mu(i)[(i,k)=1]\\ =&\sum_{a|k}\mu(a)\sum_{i=1}^{\lfloor\frac{n}{a}\rfloor}\mu(ia)\\ =&\sum_{a|k}\mu^2(a)\sum_{i=1}^{\lfloor\frac{n}{a}\rfloor}\mu(i)[(i,a)=1]\\ =&\sum_{a|k}\mu^2(a)g(\lfloor\frac{n}{a}\rfloor,a) \end{aligned} \] 这个式子暴力推，\(g\) 到边界亚线性筛。
2. 展开 \([(i,k)=1]\)。
博主一开始没有想到展开这个，但是这样推相对简单。
\[ \begin{aligned} &\sum_{i=1}^n\sum_{j=1}^m[(j,k)=1][(i,j)=1]\\ =&\sum_{a|k}\mu(a)\sum_{i=1}^n\sum_{j=1}^{\lfloor\frac{m}{a}\rfloor}[(i,ja)=1]\\ =&\sum_{a|k}\mu(a)\sum_{i=1}^n\sum_{j=1}^{\lfloor\frac{m}{a}\rfloor}[(i,j)=1][(i,a)=1] \end{aligned} \]
可以发现最后的式子和第一个式子很像，式子答案为 \(f(n,m,k)\)，那么就有 \(f(n,m,k)=\sum_{a|k}f(\lfloor\frac{m}{a}\rfloor,n,a)\)。到边界直接算即可。
可以发现对不同的地方展开，有两个截然不同的结果，虽然最后都可以得到正确答案，但是会有不同的推导难度。
而不管用什么，最重要的部分都是等效替代，也就是说把某个求和式设成函数 \(f\)，然后在推导中注意看式子中有没有重新得到 \(f\)，然后就可以得到 \(f\) 之间的递推式了。