HDU5382 GCD?LCM!

题意：令 $f(n) = \displaystyle \sum_{i = 1} ^ n \sum_{j = 1} ^ n [\text{lcm}(i, j) + \gcd(i, j)\geq n]$，求 $f(n)$ 的前缀和。$T(T\leq 10 ^ 5)$ 组数据，$n\leq 10 ^ 5$。

看着 $\text{lcm}(i, j) + \gcd(i, j) \geq n$ 有点奇怪，可以考虑递推，从 $f(n - 1)$ 递推到 $f(n)$。

容易发现多出来的部分是 $(n, x)$ 和 $(x, n)$ 的二元组，直接合法，答案加上 $2 * n - 1$。但是注意到原来的 $[\text{lcm}(i, j) + \gcd(i, j) = n - 1]$ 的二元组变得不合法了，所以我们只需要记 $\displaystyle g(n) = \sum_{i = 1} ^ n\sum_{j = 1} ^ n [\text{lcm}(i, j) + \gcd(i, j) = n]$ 即可递推得到 $f(n) = f(n - 1) - g(n - 1) + 2n - 1$。

然后看到 $=$ 就比较好做了，直接考虑莫比乌斯反演：

$$\begin{aligned} g(n) =& \sum_{i = 1} ^ n \sum_{j = 1} ^ n [\text{lcm}(i, j) + \gcd(i, j) = n]\\ =& \sum_{i = 1} ^ n \sum_{j = 1} ^ n \sum_{d = 1} ^ n [\gcd(i, j) = d] [\dfrac{ij}d + d = n]\\ =& \sum_{d = 1} ^ n \sum_{i = 1} ^ {\frac nd} \sum_{j = 1} ^ {\frac nd} [\gcd(i, j) = 1] [d(ij + 1) = n]\\ =& \sum_{d | n} \sum_{i = 1} ^ {\frac nd} \sum_{j = 1} ^ {\frac nd} [\gcd(i, j) = 1] [ij = \dfrac nd - 1] \end{aligned}$$

容易发现最后的 $i, j$ 的上界是没有意义的，我们可以直接设定为无穷大。那么考虑设 $h(n) = \sum_{i = 1} \sum_{j = 1} [\gcd(i, j) = 1][ij = n]$，那么我们可以表示 $g(n)$ 了：

$$g(n) = \sum_{d | n} h(\dfrac nd - 1)$$

容易发现我们假设知道 $h(n)$ 了，可以在 $O(n\log n)$ 的时间内得到 $g(n)$，这样也可以递推得到 $f(n)$ 了。

如何计算所有的 $h(n)$ 呢？容易发现满足 $ij\leq n$ 的二元组只有 $O(n\log n)$ 个，直接暴力枚举判断合法性就可以得到 $h(1\dots n)$，时间复杂度 $O(n\log ^ 2 n)$。

询问直接 $O(1)$ 回答。

void init()
{
	for (int i = 1; i < N; ++ i)
		for (int j = 1; i * j < N; ++ j)
			if (Gcd(i, j) == 1) f[i * j] ++;
	for (int i = 1; i < N; ++ i)
		for (int j = 1; j * i < N; ++ j)
			adj(g[i * j] += f[i - 1] - Mod);
	f[1] = 1;
	for (int i = 2; i < N; ++ i)
		adj(adj(f[i] = f[i - 1] - g[i - 1]) += 2 * i - 1 - Mod);
	for (int i = 2; i < N; ++ i) adj(f[i] += f[i - 1] - Mod);
}