# HDU 6706 – huntian oy

$${\rm gcd}(i,j)=1, i > j \rightarrow {\rm gcd}(i^a – j^a, i^b – j^b) = i^{{\rm gcd}(a,b)} – j^{{\rm gcd}(a,b)}$$

\begin{aligned} f(n, a, b) = & \sum_{i = 1}^{n} \sum_{j = 1}^{i} {\rm gcd}(i^a – j^a, i^b – j^b)[{\rm gcd}(i,j)=1] \\ = & \sum_{i = 1}^{n} \sum_{j=1}^{i} (i-j)[{\rm gcd}(i, j)=1] \\ = & \sum_{i = 1}^{n} \sum_{j = 1}^{i} i [{\rm gcd}(i, j) = 1] – \sum_{i = 1}^{n} \sum_{j = 1}^{i} j[{\rm gcd}(i, j) = 1] \end{aligned}

$$f(n, a, b) = \frac{\sum_{i = 1}^{n} i \varphi(i) – 1}{2}$$

$f(x) = x \varphi(x)$是积性函数，考虑使用筛法。设$g(x) = x$，令$f$和$g$做Direclet卷积：

$$f * g (x) = \sum_{d|x} \frac{x}{d} \varphi(\frac{x}{d}) d = \sum_{d|n} x \varphi(\frac{x}{d}) = x \sum_{d|n} \varphi(\frac{x}{d}) = x^2$$

\begin{aligned} \frac{n(n+1)(2n + 1)}{6} = \sum_{x = 1}^{n} f * g(x) =& \sum_{x = 1}^{n} \sum_{d|x} x \varphi(\frac{x}{d}) \\ = & \sum_{d=1}^{n}\sum_{x=1}^{n} x \varphi(\frac{x}{d}) [d | x] \\ = & \sum_{d=1}^{n} \sum_{x = 1}^{\lfloor \frac{n}{d} \rfloor} xd\varphi(x) \\ = & \sum_{d=1}^{n} d \sum_{x = 1}^{\lfloor \frac{n}{d} \rfloor} x \varphi(x) \\ = & F(n) + \sum_{d = 2}^{n} d F(\lfloor \frac{n}{d} \rfloor) \end{aligned}

$$F(n) = \frac{n(n+1)(2n + 1)}{6} -\sum_{d = 2}^{n} d F(\lfloor \frac{n}{d} \rfloor)$$

• $f(p) = p(p – 1)$
• $f(p^k) = p^k \varphi(p^k)$，$f(p^{k+1}) = p^{k+1} \varphi(p^{k+1}) = p^{k+1} \varphi(p^k) p = p^{k+2} \varphi(p^k)$，所以$f(p^{k+1}) = p^2 f(p^k)$

50