后面推式子部分太菜了不会,写一下这道题前半部分结论的证明.
考察在 \(10\) 进制下处理循环小数的常见手法是乘上 \(10^{l}\) 之后相减为整数,这里整数不好刻画,我们刻画为小数部分相等,则对于一个既约分数 \(\frac{i}{j}\),在 \(k\) 进制下其满足是一个循环小数的充要条件是:
\[\frac{i k^l}{j} - \lfloor \frac{ik^l}{j} \rfloor = \frac{i}{j} - \lfloor \frac{i}{j} \rfloor
\]
乘上 \(j\):
\[i k^l - j\lfloor \frac{ik^l}{j} \rfloor = i - j\lfloor \frac{i}{j} \rfloor
\]
\(\bmod j\),取除掉下取整,由于这个式子的特殊性,这一步我们可以证明是充要的:
\[ik^l \equiv i (\bmod j)
\]
由于 \(\gcd(i, j) = 1\),得到:
\[k^l \equiv 1 (\bmod j)
\]
根据唯一分解,可以得到充要条件就是 \(\gcd(k, j) = 1\),因此答案为:
\[\sum_{i = 1}^n \sum_{j = 1}^n [\gcd(i, j ) = 1][\gcd (j, k) = 1]
\]
就可以进行后面的步骤了.