1 solutions

  • 0
    #include <iostream>
    #include <vector>
    using namespace std;
    
    // 计算两个数的最大公约数,使用欧几里得算法
    long long gcd(long long a, long long b) {
        return b == 0 ? a : gcd(b, a % b);
    }
    
    // 计算一个数的约数个数
    int countDivisors(long long num) {
        int count = 0;
        // 遍历从 1 到 num 的平方根
        for (long long i = 1; i * i <= num; ++i) {
            if (num % i == 0) {
                // 如果 i 是 num 的约数
                if (i * i == num) {
                    // 若 i 是 num 的平方根,只算一个约数
                    ++count;
                } else {
                    // 否则 i 和 num/i 都是约数,算两个
                    count += 2;
                }
            }
        }
        return count;
    }
    
    int main() {
        int n;
        cin >> n;
        vector<long long> numbers(n);
        for (int i = 0; i < n; ++i) {
            cin >> numbers[i];
        }
        // 先将第一个数作为初始的最大公约数
        long long commonGCD = numbers[0];
        // 遍历数组,计算所有数的最大公约数
        for (int i = 1; i < n; ++i) {
            commonGCD = gcd(commonGCD, numbers[i]);
        }
        // 计算最大公约数的约数个数
        int divisorCount = countDivisors(commonGCD);
        cout << divisorCount << endl;
        return 0;
    }
    
    
    • 1

    Information

    ID
    204
    Time
    1000ms
    Memory
    512MiB
    Difficulty
    9
    Tags
    # Submissions
    187
    Accepted
    20
    Uploaded By