欢乐赛#33题解 T4

A33698.最大公约数

1. 计算因子个数：
   • 定义函数 countFactors，用于计算一个整数的因子个数。通过从 1 到该整数的平方根进行遍历，因为如果 i 是 num 的因子，那么 num / i 也是 num 的因子（除了 i 和 num / i 相等的情况，此时只算一个）。
   • 对于每个能整除 num 的 i，先将因子个数加 2（表示 i 和 num / i 两个因子），如果 i 和 num / i 相等，就需要把多算的一次减掉，从而准确得到 num 的因子个数。
2. 处理输入并计算因子个数序列：
   • 在 main 函数中，先读取输入的 n（整数个数）和 m（目标累加和）。
   • 然后通过循环依次读取 n 个整数，对于每个读取到的整数 tmp，调用 countFactors 函数计算其因子个数，并将结果添加到向量 v 中，这样就得到了所有整数的因子个数构成的向量。
3. 排序与累加查找：
   • 使用 sort 函数对向量 v 中的因子个数进行排序，排序方式是从大到小（通过 greater<int> 指定）。
   • 接着通过循环依次累加排序后的因子个数，用变量 sum 记录累加和。在每次累加后，判断 sum 是否大于等于 m，如果满足这个条件，就输出当前的累加次数 i + 1（因为索引是从 0 开始的，所以要加 1 才是从 1 开始计数的正确索引），然后程序结束。

复杂度分析

1. 时间复杂度：
   • 计算因子个数部分：对于每个整数计算因子个数时，需要从 1 到该整数的平方根进行遍历，假设输入的整数最大值为 N，那么计算一个整数因子个数的时间复杂度大约为 $O(\sqrt{N})$。总共要计算 n 个整数的因子个数，所以这部分的时间复杂度大约为 $O(n\sqrt{N})$。
   • 排序部分：使用 sort 函数对向量 v 进行排序，一般 sort 函数的时间复杂度为 $O(nlogn)$，这里 n 是向量 v 的长度，也就是输入的整数个数。
   • 累加查找部分：通过循环依次累加向量 v 中的元素，时间复杂度为 $O(n)$。
   • 综合起来，整个程序的时间复杂度大约为 $O(n\sqrt{N} + nlogn + n)$，简化后约为 $O(n\sqrt{N} + nlogn)$。
2. 空间复杂度：
   • 主要的空间消耗在于存储每个整数的因子个数的向量 v，向量 v 的长度最大为 n，所以空间复杂度为 $O(n)$。

#include <bits/stdc++.h>

#define endl "\n"
#define debug freopen("in.txt", "r", stdin), freopen("out.txt", "w", stdout)
using namespace std;

vector<int> v;
int n, m, tmp;

// 计算因子个数
int countFactors(int num)
{
    int count = 0;
    for (int i = 1; i <= sqrt(num); ++i)
    {
        if (num % i == 0)
        {
            count += 2; // i 和 num/i 都是因子
            if (i == num / i)
                count--; // 如果 i 和 num/i 相等，则只算一个
        }
    }
    return count;
}

int main()
{
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
    {
        scanf("%d", &tmp);
        v.push_back(countFactors(tmp));
    }
    sort(v.begin(), v.end(), greater<int>()); // 对因子个数进行排序
    int sum = 0;
    for (int i = 0; i < v.size(); i++)
    {
        sum += v[i];
        if (sum >= m)
        {
            cout << i + 1 << endl;
            return 0;
        }
    }
    return 0;
}