P2303 Longge 的问题

题目大意

即求

$$ \sum_{i=1}^n \gcd(i,n) $$

分析

联想到

$$ \varphi(n) = \sum_{i=1}^n [\gcd(i,n) = 1] $$

尝试凑这个形式

$$ \begin{aligned} \sum_{i=1}^n \gcd(i,n) &= \sum_{d \mid n} d \sum_{i=1}^n [\gcd(i,n) = d] \\ &= \sum_{d \mid n} d \sum_{i=1}^{n/d} [\gcd(i,n/d) = 1] \\ &= \sum_{d \mid n} d \varphi(n/d) \end{aligned} $$

这里其实已经可以过题了，但还可以再瞎搞一下，令

$$ nf(n) = \sum_{d \mid n} d \varphi(n/d) = n\sum_{d \mid n} \frac{\varphi(d)}{d} $$

尝试证明 $f(n)$ 是一个积性函数。设 $\gcd(a,b) = 1$，有

$$ \begin{aligned} f(a)f(b) &= \left(\sum_{d_1 \mid a} \frac{\varphi(d_1)}{d_1}\right) \left(\sum_{d_2 \mid b} \frac{\varphi(d_2)}{d_2}\right)\\ &= \sum_{d_1 \mid a} \sum_{d_2 \mid b} \frac{\varphi(d_1)}{d_1} \frac{\varphi(d_2)}{d_2}\\ &= \sum_{d_1 \mid a} \sum_{d_2 \mid b} \frac{\varphi(d_1d_2)}{d_1d_2}\\ &= f(ab) \end{aligned} $$

再来推一下素数，注意 $1 \mid p^k$，有

$$ f(p^k) = \sum_{d \mid p^k} \frac{\varphi(d)}{d} = \sum_{i=0}^k \frac{\varphi(p^i)}{p^i} = k\left(1 - \frac{1}{p}\right) + 1 $$

类似于 $\varphi(m)$ 唯一分解形式，我们还有

$$ f(n) = \prod_{i=1}^sf(p_i^{k_i}) = \prod_{i=1}^s \frac{k_ip_i - k_i + p_i}{p_i} $$

于是答案即为 $nf(n)$，复杂度 $O(\sqrt{n})$。

int main() {
	ll n = rr(), ans = n;
	for (ll i = 2; i * i <= n; i++) {
		ll k = 0;
		while (n % i == 0)
			k++, n /= i;
		if (k > 0)
			ans += ans / i * k * (i - 1);
	}
	if (n > 1)
		ans += ans / n * (n - 1);
	printf("%lld", ans);
	return 0;
}