「LightOJ 1375」LCM Extreme

Description

输入 (n)，输出下面代码的执行结果：

unsigned long long allPairLcm( int n ) {
    unsigned long long res = 0;
    for( int i = 1; i <= n; i++ )
        for( int j = i + 1; j <= n; j++ )
            res += lcm(i, j); // lcm means least common multiple
    return res;
}

共 (T) 组测试数据。

Hint

(1le Tle 2 imes 10^5)
(1le nle 3 imes 10^6)

Solution

题意：求 (sumlimits_{i = 1}^n sumlimits_{j = i + 1}^n ext{lcm}(i, j) mod 2^{64}) 的值。

直接求显然是 (O(n^2)) 的，不能这样做。

首先要知道，原式与 (sumlimits_{i = 2}^n sumlimits_{j = 1}^{i - 1} ext{lcm}(i, j)) 等价。(下文省略 (mod 2^{64}))

设 (s(x) = sumlimits_{i = 1}^{x - 1} ext{lcm}(i, x)) ，那么答案就是 ( ext{ans} = sumlimits_{i = 2}^n s(i)) 。

这相当于暗示着， 只要能在可行的时间内预处理出 (s(x)) 的值并做一遍前缀和 ，答案就可以在时间内解出。

求 (s(x)) ——推式子：

[s(x) = sumlimits_{i = 1}^{x - 1} ext{lcm}(i, x) = sumlimits_{i = 1}^{x - 1} frac{i imes x}{gcd(i, x)} = x imes sumlimits_{i = 1}^{x - 1} dfrac{i}{gcd(i, x)} ]

以上都应该非常好理解，但最后一个式子看起来非常棘手，使用常规的处理方法貌似无从下手。

对于那个 (gcd) 我们逆向思维一下—— 主动枚举 (gcd) !

[s(x) = x imes sumlimits_{g|x} sumlimits_{i = 1}^{x - 1} dfrac{i}{g}[gcd(i, x) = g] ]

其中 (g) 是所要枚举的 (gcd) ，而 (g|x) 是因为这个最大公约数一定是 (x) 的约数。

这个中括号表示，仅当 (gcd(i, x) = g) 成立是，这个对应的 (frac{i}{g}) 的值才能加上去。这相当于是对 (i) 值的一个约束。

然而这样的变形貌似效率更低了，我们尝试一下缩小枚举 (i) 的范围：

[s(x) = x imes sumlimits_{g|x} sumlimits_{i = 1}^{frac{x}{g}-1} dfrac{ig}{g}[gcd(x, ig) = g] = x imes sumlimits_{g|x} sumlimits_{i = 1}^{frac{x}{g}-1} i[gcd(frac{x}{g}, i) = 1] ]

我们发现 (i) 的枚举范围从 ([1, x)) 缩成了 ([1, frac{x}{g})) ——直接让 (i) 枚举 (g) 的倍数，因为如果不是倍数，那么 (gcd(i, x) = g) 显然不成立。

在最后一个式子里有一个 (sumlimits_{i = 1}^{frac{x}{g}-1} i[gcd(frac{x}{g}, i) = 1]) ，我们可以把它翻译为：小于 (frac{x}{g}) 的，并与 (frac{x}{g}) 互质的数之和。

这样就好办了啊，我们有一个有关于欧拉函数的性质：

小于 (n)，且与 (n) 互质的数之和等于 (dfrac{n imes varphi(n)}{2})

把上面这个的东西换到上面的式子中去，易得：

[s(x) = x imes largesumlimits_{g|x} dfrac{frac{x}{g} imes varphi(frac{x}{g})}{2} ]

可以开始设计我们的算法了：

筛出 (varphi(1) cdots varphi(n))，其中 (n) 为其对应数据规模的最大值（即 (3 imes 10^6)），下同。筛法用 (O(nlog n)) 的就够了，常数小可以应付。
预处理 (s(1)cdots s(n))，用枚举一个数的倍数的方法来处理，详见代码，复杂度 (O(nlog n))。
直接在 (s) 上滚动做前缀和。
对于每个询问，(O(1)) 给出答案。

时间复杂度 (O(nlog n + T)) ，空间复杂度 (O(n))。

Code

/*
 * Author : _Wallace_
 * Source : https://www.cnblogs.com/-Wallace-/
 * Problem : LightOJ 1375 LCM Extreme
 */
#include <cstdio>

using namespace std;
const int N = 5e6 + 5;

int phi[N];
void initPhi(int n) {
	for (register int i = 1; i <= n; i++)
		phi[i] = i;
	for (register int i = 1; i <= n; i++)
		for (register int j = i << 1; j <= n; j += i)
			phi[j] -= phi[i];
}

unsigned long long s[N];
void initSum(int n) {
	for (register int g = 2; g <= n; g++)
		for (register int x = g; x <= n; x += g)
			s[x] += phi[g] * 1ULL * g / 2 * x;
	for (register int i = 2; i <= n; i++)
		s[i] += s[i - 1];
}

signed main() {
	initPhi(3e6), initSum(3e6);
	int T; scanf("%d", &T);
	for (register int tc = 1; tc <= T; tc++) {
		int n; scanf("%d", &n);
		printf("Case %d: %llu
", tc, s[n]);
	}
}