最大公约数之和

题目描述

龙哥现在有一道题，要考考大家。

给定一个整数 $N$，请你求出 $\sum_{1 \le i \le N} \gcd(i, N)$ 的值。

输入格式

一个整数 $N$。

输出格式

一个整数表示结果。

数据范围

$1 < N < 2^{31}$

输入样例

6

输出样例

15

样例解释

对于 $N = 6$，需要计算：

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

分别计算：

• $\gcd(1, 6) = 1$
• $\gcd(2, 6) = 2$
• $\gcd(3, 6) = 3$
• $\gcd(4, 6) = 2$
• $\gcd(5, 6) = 1$
• $\gcd(6, 6) = 6$

总和：$1 + 2 + 3 + 2 + 1 + 6 = 15$

输出：15

问题分析

直接计算不可行

由于 $N$ 最大可达 $2^{31} - 1 \approx 2.1 \times 10^9$，直接枚举 $i$ 从 $1$ 到 $N$ 计算 $\gcd(i,N)$ 是不可能的（时间复杂度 $O(N \log N)$）。

数学转化

考虑 $\gcd(i, N)$ 的可能取值：它们必须是 $N$ 的约数。

设 $d$ 是 $N$ 的一个正约数，我们来计算有多少个 $i$（$1 \le i \le N$）满足 $\gcd(i, N) = d$。

如果 $\gcd(i, N) = d$，那么：

1. $d \mid i$（$d$ 整除 $i$）
2. $d \mid N$（$d$ 整除 $N$）
3. $\gcd\left(\frac{i}{d}, \frac{N}{d}\right) = 1$

令 $i' = i/d$，$N' = N/d$，则条件变为：

• $1 \le i' \le N'$
• $\gcd(i', N') = 1$

满足 $\gcd(i', N') = 1$ 且 $1 \le i' \le N'$ 的 $i'$ 的个数就是欧拉函数 $\varphi(N')$。

因此：

$$\sum_{i=1}^{N} \gcd(i, N) = \sum_{d \mid N} d \cdot \varphi\left(\frac{N}{d}\right)$$

其中求和是对 $N$ 的所有正约数 $d$ 进行。

对称形式

利用约数对称性，上式也可以写成：

$$\sum_{i=1}^{N} \gcd(i, N) = \sum_{d \mid N} \frac{N}{d} \cdot \varphi(d)$$

两种形式等价，因为如果 $d$ 遍历 $N$ 的所有约数，那么 $N/d$ 也遍历 $N$ 的所有约数。

计算方法

步骤

1. 分解质因数：对 $N$ 进行质因数分解
2. 生成所有约数：根据质因数分解生成 $N$ 的所有约数
3. 计算欧拉函数：对每个约数 $d$，计算 $\varphi(d)$
4. 求和：计算 $\sum_{d \mid N} \frac{N}{d} \cdot \varphi(d)$

质因数分解

由于 $N < 2^{31}$，使用试除法分解质因数：

• 只需试除到 $\sqrt{N}$（约 $46340$）
• 注意 $N$ 本身可能是大质数

生成约数

设 $N = p_1^{a_1} p_2^{a_2} \cdots p_k^{a_k}$，则 $N$ 的约数个数最多约为：

• 当 $N$ 是前几个质数的乘积时，约数个数最多
• 对于 $N < 2^{31}$，约数个数最多大约在 $1500$ 左右

计算 $\varphi(d)$

如果 $d = p_1^{b_1} p_2^{b_2} \cdots p_k^{b_k}$，那么：

$$\varphi(d) = d \cdot \prod_{i=1}^{k} \left(1 - \frac{1}{p_i}\right)$$

示例计算（N=6）

质因数分解

$6 = 2^1 \times 3^1$

所有约数

$d \in \{1, 2, 3, 6\}$

计算 $\varphi(d)$

• $\varphi(1) = 1$
• $\varphi(2) = 2 \times (1 - \frac{1}{2}) = 1$
• $\varphi(3) = 3 \times (1 - \frac{1}{3}) = 2$
• $\varphi(6) = 6 \times (1 - \frac{1}{2}) \times (1 - \frac{1}{3}) = 2$

计算总和

$$\sum_{d \mid 6} \frac{6}{d} \cdot \varphi(d) = \frac{6}{1} \cdot 1 + \frac{6}{2} \cdot 1 + \frac{6}{3} \cdot 2 + \frac{6}{6} \cdot 2 = 6 + 3 + 4 + 2 = 15$$

算法优化

更高效的公式

可以推导出更简洁的公式：

$$\sum_{i=1}^{N} \gcd(i, N) = \sum_{d \mid N} \varphi(d) \cdot \frac{N}{d}$$

或者直接计算：

$$\sum_{i=1}^{N} \gcd(i, N) = N \cdot \sum_{d \mid N} \frac{\varphi(d)}{d}$$

利用积性函数

设 $f(N) = \sum_{i=1}^{N} \gcd(i, N)$，则 $f(N)$ 是积性函数。

如果 $N = p^a$（$p$ 是质数），那么：

$$f(p^a) = \sum_{i=1}^{p^a} \gcd(i, p^a) = p^a + \sum_{k=0}^{a-1} \varphi(p^k) \cdot p^{a-k}$$

简化后：

$$f(p^a) = (a+1)p^a - a \cdot p^{a-1}$$

验证 $p=2, a=2$（$N=4$）：

• $f(4) = (2+1) \cdot 4 - 2 \cdot 2 = 3 \cdot 4 - 4 = 12 - 4 = 8$
• 直接计算：$\gcd(1,4)+\gcd(2,4)+\gcd(3,4)+\gcd(4,4)=1+2+1+4=8$ ✓

对于一般的 $N = p_1^{a_1} p_2^{a_2} \cdots p_k^{a_k}$：

$$f(N) = \prod_{i=1}^{k} \left[(a_i+1)p_i^{a_i} - a_i \cdot p_i^{a_i-1}\right]$$

最终算法

1. 对 $N$ 进行质因数分解：$N = p_1^{a_1} p_2^{a_2} \cdots p_k^{a_k}$
2. 计算：$$\text{答案} = \prod_{i=1}^{k} \left[(a_i+1)p_i^{a_i} - a_i \cdot p_i^{a_i-1}\right]$$

样例验证（N=6）

$6 = 2^1 \times 3^1$

• 对于 $p=2, a=1$：$(1+1) \cdot 2^1 - 1 \cdot 2^{0} = 2 \cdot 2 - 1 = 4 - 1 = 3$
• 对于 $p=3, a=1$：$(1+1) \cdot 3^1 - 1 \cdot 3^{0} = 2 \cdot 3 - 1 = 6 - 1 = 5$
• 乘积：$3 \times 5 = 15$ ✓

时间复杂度

• 质因数分解：$O(\sqrt{N})$，最坏情况 $N$ 是质数时需要试除到 $\sqrt{N}$
• 公式计算：$O(k)$，其中 $k$ 是不同质因数的个数

对于 $N < 2^{31}$，$\sqrt{N} < 46340$，可以接受。

注意事项

1. 使用 long long 类型存储结果，因为答案可能很大
2. 注意乘法可能溢出，及时取模（但题目没有要求取模）
3. $N > 1$，所以至少有一个质因数

时空限制

• 时间限制：1秒
• 空间限制：64MB