企业官网建设流程全解析

看到 E - Sum of gcd of Tuples (Hard) 这个标题，我第一反应是：这又是一道用 “Hard” 吓唬人、实际考数论基本功的计数题。题目给两个数 N 和 K，要求所有长度为 N、每个元素都在 1 到 K 之间的 tuple，求它们 gcd 的和，结果对 1e9+7 取模。直接枚举 K^N 个 tuple 显然不现实，Hard 的点不在于模拟，而在于怎么把“对 tuple 求和”变成“对 gcd 的值求和”。这篇文章我会把两种解法都摊开讲：一种是先从倍数关系倒推“恰好 gcd”的容斥，另一种是利用欧拉函数直接得到公式。前者直观，后者代码更短，建议两个都学会。

1. 先弄明白题目到底在问什么

1.1 形式化定义

输入两个整数 N、K。考虑集合：

[ A = { (a_1, a_2, \dots, a_N) \mid 1 \le a_i \le K } ]

每个元素 a_i 都是 1 到 K 之间的整数，tuple 是有顺序的，也就是 (1, 2) 和 (2, 1) 算两个不同元素。集合 A 的大小是 K^N。

要求计算：

[ S = \sum_{(a_1,\dots,a_N) \in A} \gcd(a_1,\dots,a_N) ]

最后对 M = 1e9+7 取模。这里的 gcd 是 N 个数的最大公约数。N=1 的时候，gcd 就是 a_1 本身，所以答案等于 1+2+...+K；这个特殊 case 可以用来验证代码。

1.2 Hard 难在规模，不在概念

这道题的概念非常简单，难在数据范围。常规约束下 N 和 K 都可能到 1e5。此时 K^N 是一个天文数字，不要说枚举，就算只看一个 K=10, N=10 的小例子，枚举量也是 100 亿。

所以正确思路不是去遍历 tuple，而是去遍历可能的 gcd 值。任意一个 tuple 的 gcd 只可能是 1 到 K 之间的整数，于是可以把答案改写成：

[ S = \sum_{g=1}^{K} g \times cnt_g ]

其中 cnt_g 表示“gcd 恰好等于 g”的 tuple 数量。到这里，核心问题变成了：怎么高效算出 cnt_g。

1.3 先看一个小例子建立感觉

取 N=2, K=3。所有 9 个二元组分别是：

(1,1)、(1,2)、(1,3)、(2,1)、(2,2)、(2,3)、(3,1)、(3,2)、(3,3)

它们的 gcd 分别是 1、1、1、1、2、1、1、1、3，总和是 12。

这个例子里 cnt_1=7，cnt_2=1，cnt_3=1。验证一下：7×1 + 1×2 + 1×3 = 12。注意 gcd=1 的 tuple 数量占了大多数，说明如果直接把“所有元素都是 1 的倍数”当成“gcd=1”来算，会错得离谱。

2. 核心思路：F(d) 和 f(d) 的倍数关系

2.1 定义两个关键计数函数

定义：

• F(d)：gcd 是 d 的倍数的 tuple 数量。
• f(d)：gcd 恰好等于 d 的 tuple 数量。

要计算 F(d)，只需要让每个 a_i 都是 d 的倍数。1 到 K 中 d 的倍数有 floor(K/d) 个，每个位置独立选择，所以：

[ F(d) = \left\lfloor \frac{K}{d} \right\rfloor ^ N ]

这个式子非常好算，用快速幂就能在 O(log N) 时间内得到。

2.2 F(d) 是所有“更大倍数”的叠加

如果某个 tuple 的 gcd 是 d 的倍数，那么 gcd 一定等于 d、2d、3d……中的某一个。所以有：

[ F(d) = f(d) + f(2d) + f(3d) + \dots + f(\lfloor K/d \rfloor \cdot d) ]

换句话说，F(d) 是所有 gcd 为 d 的倍数的 f 值之和。这个恒等式是整套解法的地基。

反过来看，如果我能先算出所有更大的 f(2d)、f(3d)……那么用 F(d) 减去它们，就能得到 f(d)。这就是容斥。

2.3 倒着减：为什么必须从 K 往 1 算

计算 f(d) 的时候，需要用到更大的 f(2d)、f(3d) 等。所以循环顺序必须从大到小，先算大的，再算小的。伪代码如下：

for (int d = K; d >= 1; --d) { f[d] = pow_mod(K / d, N); for (int t = d + d; t <= K; t += d) { f[d] -= f[t]; } }

这里 t 从 2d 开始，依次是 3d、4d……一直到不超过 K。因为循环是从 K 往下走的，所以当处理到 d 时，所有比 d 大的 f[t] 都已经算好了，可以放心减。

一旦拿到 f(d)，就累加答案：

[ ans = ans + d \times f(d) \pmod M ]

整个过程不需要求逆元，不需要莫比乌斯函数，只要一个整除循环和快速幂。

2.4 复杂度：K log K，听上去可怕，实际很小

内层循环的总次数是：

[ \frac{K}{1} + \frac{K}{2} + \frac{K}{3} + \dots + \frac{K}{K} ]

约等于 K ln K。K=1e5 时大约是 120 万次，完全无压力。再加上每个 d 都要跑一次快速幂，总共 O(K log N) 次乘法，也仍然很快。空间上只需要一个长度为 K+1 的数组存 f，O(K)。

3. 代码落地：倍数容斥版本

3.1 完整可跑代码

#include <bits/stdc++.h> using namespace std; using int64 = long long; const int64 MOD = 1000000007LL; int64 mod_pow(int64 a, int64 e) { int64 res = 1; while (e) { if (e & 1) res = res * a % MOD; a = a * a % MOD; e >>= 1; } return res; } int main() { int N, K; cin >> N >> K; vector<int64> f(K + 1, 0); int64 ans = 0; for (int d = K; d >= 1; --d) { int64 cur = mod_pow(K / d, N); for (int t = d + d; t <= K; t += d) { cur -= f[t]; if (cur < 0) cur += MOD; } f[d] = cur; ans = (ans + (int64)d * cur) % MOD; } cout << ans << '\n'; return 0; }

这个版本应该是所有解法里最好理解的。核心循环就是“先算 F(d)，再减掉所有更大的 f(multiple)”。

3.2 代码里的三个小细节

第一个细节，K / d 在 C++ 里自动下取整，刚好对应 floor(K/d)。第二个细节，cur 在减去 f[t] 之后可能变成负数，因为 f[t] 是取模后的值，不是真实值。这里每次减完都判断一次，如果小于 0 就加一个 MOD，保证 cur 始终是非负且小于 MOD 的余数。

第三个细节是 ans 累加时一定要用 long long。d 最大 1e5，cur 最大接近 1e9，两者相乘是 1e14 级别，int 会直接溢出。比赛里很多次 AC 变 WA 就是差在这个类型上。

3.3 一个可选常数优化：缓存 K/d 的幂

在循环里反复执行 mod_pow(K / d, N)，虽然不慢，但可以继续压一压。注意 K/d 的取值并不连续，常见值只有 O(sqrt(K)) 个。开一个缓存数组，遇到相同的商直接取结果：

vector<int64> power_cache(K + 1, -1); for (int d = K; d >= 1; --d) { int v = K / d; if (power_cache[v] == -1) { power_cache[v] = mod_pow(v, N); } int64 cur = power_cache[v]; // 后面同样做倍数容斥 }

这个优化在 K=1e5 时不明显，但思路值得记住：当同一底数反复出现时，用记忆化代替重复快速幂。

4. 更漂亮的解法：欧拉函数直接出答案

4.1 用到一个经典恒等式

对于任意正整数 x，有：

[ x = \sum_{d \mid x} \varphi(d) ]

这背后的直观理解是：把 1 到 x 这些数按“和 x 的最大公约数”分组，每一组的数量恰好是某个 phi 值，加回来正好是 x。虽然说起来抽象，但这个恒等式非常实用。

把它作用在 gcd 上：

[ \gcd(a_1,\dots,a_N) = \sum_{d \mid \gcd(a_1,\dots,a_N)} \varphi(d) ]

d 遍历的是 gcd 的所有因子。

4.2 交换求和顺序，一步到答案

把上面的恒等式代回原式：

[ S = \sum_{tuple} \sum_{d \mid gcd(tuple)} \varphi(d) ]

交换求和顺序，先枚举 d，再统计有多少个 tuple 满足 d 是 gcd 的因子。要满足 d | gcd(tuple)，等价于每个 a_i 都是 d 的倍数，数量就是：

[ \left\lfloor \frac{K}{d} \right\rfloor ^ N ]

于是：

[ S = \sum_{d=1}^{K} \varphi(d) \times \left\lfloor \frac{K}{d} \right\rfloor ^ N ]

到这里，问题变成了：预处理 phi[1..K]，然后循环一遍，每次用快速幂算 floor(K/d)^N，再乘上 phi[d] 累加。复杂度 O(K log K) 起步，但如果 phi 用线性筛预处理，主循环 O(K log N)，比容斥版更短也更快。

4.3 用欧拉筛预处理 phi

对于 K=1e5，最简单的 phi 预处理可以用类似埃氏筛的写法：

vector<int> phi(K + 1); for (int i = 0; i <= K; ++i) phi[i] = i; for (int i = 2; i <= K; ++i) { if (phi[i] == i) { for (int j = i; j <= K; j += i) { phi[j] -= phi[j] / i; } } }

这个写法对 1e5 的 K 完全够用。之后主循环：

long long ans = 0; for (int d = 1; d <= K; ++d) { ans = (ans + (long long)phi[d] * mod_pow(K / d, N)) % MOD; } cout << ans << '\n';

K=1 时，循环不进入 phi 预处理部分，phi[1]=1，答案就是 mod_pow(1, N)=1，和实际一致。

4.4 和莫比乌斯反演的关系

前面容斥版其实是莫比乌斯反演的另一种写法。若定义 F(d)=Σ_{multiple} f(multiple)，则反解为：

[ f(d) = \sum_{m} \mu\left(\frac{m}{d}\right) F(m) ]

代进答案 S=Σd·f(d)，交换求和后可以得到同样的欧拉函数公式。只不过欧拉函数版本把容斥过程藏进了 phi 的预处理里，所以代码表面上看不到“减”的过程。

5. 实战踩坑与排错建议

5.1 常见错误速查表

这些坑我都踩过，或者说非常眼熟。尤其是“把 F 当 f”这个错误，即使思路明白，一到写代码时也容易顺手写错变量名。

5.2 对拍验证：小数据暴力枚举

不管用哪种解法，写完第一件事就是写一个暴力程序对拍。N 和 K 取很小，比如 N=2, K=3，N=3, K=4，直接枚举所有 tuple 计算 gcd 总和。

暴力代码不用写得很复杂，三层循环或者递归枚举都行。对拍逻辑是：生成若干组小 N、K，分别跑暴力版和高效版，比较输出。只要有一组不一致，先打印输出 f 数组，确认容斥时减掉的倍数集合对不对。

5.3 性能和取模经验

我按 K=1e5、N=1e5 的情况在自己机器上测过，容斥版本和欧拉函数版本都是毫秒级，完全不用担心。真正影响题解体验的其实是取模写法。

容斥版内层如果用cur = (cur - f[t] + MOD) % MOD，也能跑，但取模运算是较重的操作。用if (cur < 0) cur += MOD代替，可以省掉大量模运算。对于 1e5 级别的循环，这个优化纯粹是心理安慰级别，但既然是写题解，顺手写快一点没坏处。

5.4 遇到类似 gcd 计数题的通用套路

这类题目表面千变万化，骨子里都是同一件事：找一个容易算的“倍数计数函数”，再通过倍数关系还原“恰好计数函数”。比如让你求所有 tuple 的 gcd 平方和、gcd 的 k 次方和，框架都不用改，只要在累加答案时把 d 换成 d^c，再用快速幂处理幂次即可。

如果 dp 里还要求 gcd 刚好为某个固定值，思路也是一样的。先写 F(d)=floor(K/d)^N，再倒着减出 f(d)。记住这个套路，以后看到类似的 Hard 题就不会慌。我个人现在更倾向于直接用欧拉函数公式，代码短、思路干净；但如果题目还要求输出每个 gcd 的分布，那还是老老实实把 f 数组完整算出来更稳。