B. Crimson Triples（Codeforces 2238）

B. Crimson Triples - 题解

题意简述

给定n，要统计有多少个有序三元组(a, b, c)满足：

1 <= a, b, c <= n

并且：

gcd(lcm(a, b), lcm(b, c)) = gcd(a, c)

注意三元组是有序的，(1, 2, 3)和(3, 2, 1)算不同。

核心结论

一个三元组(a, b, c)满足条件，当且仅当：

b | a 且 b | c

也就是b同时整除a和c。

接下来解释为什么。

从质因数指数理解

任意正整数都可以拆成质因数。
我们只看某一个质因子p。

设p在a, b, c中出现的次数分别为：

x = v_p(a) y = v_p(b) z = v_p(c)

例如：

a = 12 = 2^2 * 3^1 v_2(12) = 2 v_3(12) = 1

对于质因数指数，有两个基本规则：

v_p(gcd(u, v)) = min(v_p(u), v_p(v)) v_p(lcm(u, v)) = max(v_p(u), v_p(v))

所以原式左边在质因子p上的指数是：

v_p(gcd(lcm(a, b), lcm(b, c))) = min(max(x, y), max(y, z))

右边在质因子p上的指数是：

v_p(gcd(a, c)) = min(x, z)

因此要求：

min(max(x, y), max(y, z)) = min(x, z)

化简这个条件

观察左边：

max(x, y) >= y max(y, z) >= y

所以：

min(max(x, y), max(y, z)) >= y

如果y > min(x, z)，那么左边至少是y，会严格大于右边，条件不成立。

如果y <= min(x, z)，说明：

y <= x 且 y <= z

于是：

max(x, y) = x max(y, z) = z

左边变成：

min(x, z)

正好等于右边。

所以对于每一个质因子，都必须且只需满足：

y <= x 且 y <= z

翻译回整数就是：

b | a 且 b | c

计数方法

固定中间的数b。

由于必须满足：

b | a b | c

所以a和c都必须是b的倍数。

在1..n中，b的倍数有：

floor(n / b)

个：

b, 2b, 3b, ..., floor(n / b) * b

a可以任选一个倍数，c也可以任选一个倍数，所以固定b时贡献为：

floor(n / b) * floor(n / b)

把所有b = 1..n的贡献加起来：

answer = sum_{b=1}^{n} floor(n / b)^2

图表示意

以n = 6为例：

总答案：

36 + 9 + 4 + 1 + 1 + 1 = 52

也可以这样理解：

固定 b a 的选择：b, 2b, 3b, ... c 的选择：b, 2b, 3b, ... 每一个 a 都可以和每一个 c 配对，所以是一个 m * m 的方阵。

算法流程

对每个测试用例：

1. 读入n；
2. 初始化ans = 0；
3. 枚举b从1到n；
4. 令m = n / b；
5. 累加ans += m * m；
6. 输出ans。

易错点

1. 三元组是有序的，a和c不能合并计数。
2. 不是统计gcd(a, c)的值，而是统计所有满足条件的(a, b, c)。
3. 答案可能很大，必须使用long long。例如n = 200000时，光是b = 1的贡献就是200000^2 = 40000000000。
4. 题目保证所有测试用例的n之和不超过2 * 10^5，所以每个测试用例直接O(n)枚举是足够的。

复杂度分析

设所有测试用例的n之和为S。

时间复杂度：O(S) 空间复杂度：O(1)

其中题目保证S <= 2 * 10^5。

C++ 代码实现

#include<bits/stdc++.h>usingnamespacestd;intmain(){ios::sync_with_stdio(false);cin.tie(nullptr);intT;cin>>T;while(T--){longlongn;cin>>n;longlongans=0;// 固定中间的 b。// 条件等价于 b | a 且 b | c。// 在 1..n 中，b 的倍数有 floor(n / b) 个。for(longlongb=1;b<=n;++b){longlongmultiples=n/b;ans+=multiples*multiples;}cout<<ans<<'\n';}return0;}