最大公约数最大化：代码实现与优化

题目描述：

给你一行 n 个数 a[i]，你可以选择任意一个 a[i]，然后将其修改为任意数值，使得所有 n 个数的最大公约数最大。

请给出修改数列后的最大公约数。

数据格式：

输入格式： 第一行一个整数 n，第二行 n 个整数 a[i]。
输出格式： 输出一个整数，表示修改数列后的最大公约数。

样例：

输入数据 1 3 4 5 6
输出数据 1 2
输入数据 2 3 8 9 72
输出数据 2 9

数据范围：

1 <= n <= 10^5

1 <= a[i] <= 10^9

注意：

需要读写文件，读入文件名为 gcd.in，输出文件名为 gcd.out

C++ 代码实现：

#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>

using namespace std;

int gcd(int a, int b) {
    if (b == 0) {
        return a;
    }
    return gcd(b, a % b);
}

int main() {
    ifstream fin("gcd.in");
    ofstream fout("gcd.out");

    int n;
    fin >> n;

    vector<int> nums(n);
    for (int i = 0; i < n; i++) {
        fin >> nums[i];
    }

    int maxGcd = 0;
    for (int i = 0; i < n; i++) {
        vector<int> temp(nums);
        for (int j = 1; j <= 100; j++) {
            temp[i] = j;
            int currGcd = temp[0];
            for (int k = 1; k < n; k++) {
                currGcd = gcd(currGcd, temp[k]);
            }
            maxGcd = max(maxGcd, currGcd);
        }
    }

    fout << maxGcd << endl;

    fin.close();
    fout.close();

    return 0;
}

代码优化：

减少循环次数： 原始代码中，对每个数字 a[i] 都尝试了 1 到 100 的所有数值，可以优化为只尝试 a[i] 的因子，这样可以显著减少循环次数。
使用更快的 GCD 算法： 可以使用更快的 GCD 算法，例如欧几里得算法，来提高计算效率。
避免重复计算： 可以记录每个数字的因子，避免重复计算 GCD。

优化后的代码：

#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <unordered_map>

using namespace std;

int gcd(int a, int b) {
    if (b == 0) {
        return a;
    }
    return gcd(b, a % b);
}

vector<int> getFactors(int num) {
    vector<int> factors;
    for (int i = 1; i * i <= num; i++) {
        if (num % i == 0) {
            factors.push_back(i);
            if (i * i != num) {
                factors.push_back(num / i);
            }
        }
    }
    return factors;
}

int main() {
    ifstream fin("gcd.in");
    ofstream fout("gcd.out");

    int n;
    fin >> n;

    vector<int> nums(n);
    for (int i = 0; i < n; i++) {
        fin >> nums[i];
    }

    unordered_map<int, vector<int>> factors;
    for (int i = 0; i < n; i++) {
        factors[nums[i]] = getFactors(nums[i]);
    }

    int maxGcd = 0;
    for (int i = 0; i < n; i++) {
        for (int factor : factors[nums[i]]) {
            nums[i] = factor;
            int currGcd = nums[0];
            for (int j = 1; j < n; j++) {
                currGcd = gcd(currGcd, nums[j]);
            }
            maxGcd = max(maxGcd, currGcd);
        }
    }

    fout << maxGcd << endl;

    fin.close();
    fout.close();

    return 0;
}

优化后的代码使用了以下方法：

使用 getFactors() 函数获取每个数字的因子。
使用 unordered_map 存储每个数字的因子，避免重复计算。
仅对每个数字的因子进行尝试，减少了循环次数。

通过这些优化，代码的效率得到了显著提升。