喵~ 各位同学好呀！今天本猫娘要给大家带来 Codeforces 上一道非常经典又可爱的题目——C. Common Divisors 的题解分析哦！
这道题就像是在一大堆毛线球里，找出能完美缠绕所有毛线球的线芯一样，是不是很有趣呢？那么，就跟着我一起来看看怎么解决它吧，喵~
题目大意
这道题的要求其实很简单哦，听我慢慢道来~
题目会给我们一个包含 n 个正整数的数组 a。我们的任务就是，找到到底有多少个正整数 x，这个 x 能够整除数组 a 中的 每一个 数字。
换句话说，就是要我们找出数组 a 中所有元素的 公共约数 的数量。
举个例子吧，喵~ 如果数组是 a = [2, 4, 6, 2, 10]：
1可以整除 2, 4, 6, 2, 10。2可以整除 2, 4, 6, 2, 10。- 其他像
3,4这样的数就不能整除所有的数了。
所以，公共约数就是 1 和 2，总共有 2 个。我们的答案就是 2 啦！
解题思路
看到这个问题，大家的第一反应可能是：呜哇，要检查每一个数对数组里所有元素的关系，会不会很麻烦呀？
别担心！这里有一个非常重要的数学性质，能让问题瞬间变得简单起来，就像猫咪找到了最舒服的纸箱一样！
核心思想： 一个数组中所有元素的 公共约数 集合，等价于这些元素 最大公约数 (GCD) 的约数 集合。
是不是感觉眼前一亮，喵？也就是说，我们根本不需要去关心数组里那 n 个复杂的数字，我们只需要关心它们的「最大公约数」这一个数就行了！
所以，我们的解题步骤就清晰地分成了两步：
第一步：求出数组中所有元素的最大公约数 (GCD)。 我们可以先计算第一个和第二个数的 GCD，得到一个结果
g。然后用这个g和第三个数计算新的 GCD，再用新的结果和第四个数计算……以此类推，像滚雪球一样，滚到最后，得到的就是整个数组所有元素的 GCD 啦。第二步：计算这个 GCD 的约数个数。 当第一步完成后，问题就转化成了一个更简单的问题：“求一个数
g有多少个约数”。这个就简单多啦，对吧？
代码解说
下面我们来看看具体的 C++ 代码是怎么实现这个思路的，喵~
#include <iostream>
#include <numeric> // For std::gcd
// The main idea is that the set of common divisors of a list of numbers
// is identical to the set of divisors of their greatest common divisor (GCD).
// So, the problem breaks down into two steps:
// 1. Calculate the GCD of all numbers in the input array.
// 2. Count the number of divisors of the resulting GCD.
int main() {
// Fast I/O for performance
std::ios_base::sync_with_stdio(false);
std::cin.tie(NULL);
int n;
std::cin >> n;
// The values of a_i can be up to 10^12, so we must use a 64-bit integer type.
long long g;
std::cin >> g;
// Step 1: Calculate the GCD of all numbers in the array.
// We can do this iteratively. Initialize g with the first element,
// then for each subsequent element, update g to be the GCD of the current g
// and the new element. std::gcd is available since C++17.
for (int i = 1; i < n; ++i) {
long long a;
std::cin >> a;
g = std::gcd(g, a);
}
// Step 2: Count the number of divisors of the resulting GCD 'g'.
// A naive loop from 1 to g would be too slow since g can be up to 10^12.
// An efficient method is to iterate from 1 up to the square root of g.
long long divisor_count = 0;
// The loop variable 'i' must be long long to prevent overflow in 'i * i'.
for (long long i = 1; i * i <= g; ++i) {
if (g % i == 0) {
// If 'i' is a divisor, then 'g / i' is also a divisor.
if (i * i == g) {
// If 'i' is the square root of g, it's a single divisor.
// We count it just once to avoid duplication.
divisor_count++;
} else {
// Otherwise, 'i' and 'g / i' form a pair of distinct divisors.
divisor_count += 2;
}
}
}
std::cout << divisor_count << std::endl;
return 0;
}输入和类型
std::ios_base::sync_with_stdio(false); std::cin.tie(NULL);这两行是为了加速 C++ 的输入输出，在处理大量数据时是个好习惯，喵~long long g;题目中a_i的值最大可以到10^12，普通的int类型是存不下的，会溢出！所以我们必须用long long来存储 GCD 和数组中的元素。
计算 GCD
std::cin >> g;先读入第一个数，作为 GCD 的初始值。for (int i = 1; i < n; ++i)循环从第二个数开始，依次读入。g = std::gcd(g, a);这一行是核心！std::gcd是 C++17 标准库里提供的函数，可以直接计算两个数的最大公约数。我们用它来不断更新g的值，最终得到的g就是所有元素的 GCD。
计算约数个数
- 这里的
g可能非常大（最大10^12），如果我们从 1 循环到g来找约数，肯定会超时。所以我们用了一个聪明的办法！ for (long long i = 1; i * i <= g; ++i)我们只循环到g的平方根。为什么呢？因为约数都是成对出现的！如果i是g的约数，那么g / i也一定是g的约数。if (g % i == 0)判断i是否为约数。if (i * i == g)这是一个特殊情况。如果g是一个完全平方数（比如 36），那么它的平方根（比如 6）和g除以它的平方根是同一个数。这个时候，我们只找到了一个约数，所以divisor_count只加 1。else { divisor_count += 2; }如果不是完全平方数，那么i和g / i就是一对不同的约数，所以divisor_count直接加 2。
- 这里的
这样一来，我们就能高效地解决问题啦！
知识点介绍
这道题涉及了两个非常基础但重要的数论知识点，本猫娘来给大家科普一下~
1. 最大公约数 (Greatest Common Divisor, GCD)
- 定义：最大公约数是指，在两个或多个整数的所有公共约数中，最大的那一个。例如，12 和 18 的公共约数有 1, 2, 3, 6，其中最大的就是 6，所以
gcd(12, 18) = 6。 - 重要性质：GCD 满足结合律，即
gcd(a, b, c) = gcd(gcd(a, b), c)。正是这个性质，让我们能够通过迭代的方式，两两计算，最终求得整个数组的 GCD。
2. 高效地求一个数的约数个数
对于一个数 N，如何快速求出它有多少个约数呢？
- 朴素方法：从 1 循环到
N，检查每个数i是否能整除N。当N很大时（比如10^12），这个方法太慢了，会超时。 - 平方根优化法：
- 约数是成对出现的。如果
i是N的约数，那么N / i也必然是N的约数。例如，对于N=30，2是约数，那么30/2=15也是约数；3是约数，30/3=10也是。 - 我们可以只遍历从
1到sqrt(N)的数i。 - 每当我们找到一个约数
i，我们就同时找到了另一个约数N / i。所以约数个数+2。 - 特别注意：如果
N是一个完全平方数，比如N=36，当i=6时，i和N/i是同一个数。为了避免重复计数，这种情况只能算作一个约数，个数+1。
- 约数是成对出现的。如果
好啦，今天的解题小课堂就到这里了，喵~ 希望大家通过这道题，对 GCD 和约数计数有了更深的理解！我们下次再见啦！