HDU 1695：使用欧拉函数与容斥原理解决最大公约数问题

"HDU 1695 GCD（欧拉函数+容斥原理）问题解析及解题思路" 该题目是HDU（杭州电子科技大学）在线评测系统中的一道编程竞赛题，主要考察了欧拉函数（Euler's Totient Function）和容斥原理在解决数论问题中的应用。题目要求找到所有满足条件的整数对 (x, y)，其中 x 属于 [1, b] 范围，y 属于 [1, d] 范围，并且它们的最大公约数（Greatest Common Divisor，GCD）等于给定的整数 k。 首先，理解题目中的关键概念： 1. **欧拉函数**：欧拉函数 φ(n) 表示小于等于 n 的正整数中与 n 互质的数的数量。例如，φ(4) = 2，因为1和3与4互质；φ(6) = 2，因为1和5与6互质。 其次，解题策略分为两步： 1. 当 y = a 时，问题简化为求 1 到 a/k 之间的欧拉函数的累计和，因为对于每个 x 在 [1, b/k] 内，都存在唯一的 y 在 [1, a] 内使得 g(x, y) = k。 2. 当 y ≠ a 时，情况变得复杂，此时无法直接利用欧拉函数。这里需要应用 **容斥原理**。容斥原理是组合数学中的一种方法，用于计算集合中元素的个数。在这个问题中，我们需要计算在 1 到 b/k 范围内，与 y 互质的数的数量，而 y 可能有某些质因数在 1 到 a 范围内有倍数。因此，我们需要找出 y 的所有质因数，并计算它们在 1 到 a 范围内的倍数，然后通过容斥原理来确定与 y 互质的数的数量。 解题代码中包含了两个关键函数： 1. `get_phi` 函数：通过厄拉多塞筛法计算欧拉函数值，用于初始化 φ 数组。 2. `init` 函数：计算每个数的质因数分解，存储在 `link` 向量中，以便后续计算。 最后，解题步骤大致如下： 1. 初始化欧拉函数表和质因数分解。 2. 对于每个可能的 k 值，计算两种情况下的对数： - 情况1：当 y = a 时，直接累加从 1 到 a/k 的欧拉函数值。 - 情况2：当 y ≠ a 时，遍历 y 的质因数，计算其在 1 到 a 范围内的倍数，然后用容斥原理计算互质对数。 3. 将两种情况的结果相加，得到最终答案。 通过这样的算法，可以有效地解决题目所给出的问题，找到所有满足条件的 (x, y) 对数。