主要思路

好题目啊。

发现 \(f(x)\) 对于有平方因子的数都没有效益，所以我们只考虑 \(f(x) = \prod_{i = 1}^m p_i\)。那么很容易发现 \(f(x) = \prod_{r = 0}^m (-1)^{2^{(r – 1)}}\)，所以：

\[ f(x) = \begin{cases} -1, x \in primes or x = 1 \\ 1, otherwise \end{cases} \]

主要思路

先考虑莫比乌斯反演？

\[ \begin{aligned} ans &= \sum_{i = 1}^n \sum_{j = 1}^n f(\gcd(i, j))^k \\ &= \sum_{d = 1}^n f(d)^k \sum_{i = 1}^n \sum_{j = 1}^n [\gcd(i, j) = d] \end{aligned} \]

经典化简：

\[ \begin{aligned} ans &= \sum_{T = 1}^n \lfloor \frac{n}{T} \rfloor^2 \sum_{x|T} \mu(x) f(\frac{T}{x})^k \end{aligned} \]

我们可以对这个 \(\lfloor \frac{n}{T} \rfloor^2\) 进行整除分块，所以问题的重心转移到了求后面那个 Dirichlet 卷积的前缀和身上。

主要思路

其实稍稍看一下，会发现 \([j|i][(j + k)|i]\) 满足的时候 \(k\) 并没有什么特别的限制，所以可以直接理解为选两个因数，然后就转化为了：

\[ \begin{aligned} & \sum_{i = 1}^n {\sigma_0(i) \choose 2} \\ =& \sum_{i = 1}^n \frac{\sigma_0^2(i) – \sigma_0(i)}{2}\end{aligned} \]

后面的那个 \(\sum \sigma_0(x)\) 可以直接数论分块，前面那个用 min_25 筛一下就好。有 \(f(p^k) = \prod (1 + c_i)^2\)。