最大公约数
(gcd.pas/c/cpp)
【问题描述】
给定 n 个正整数，a_1,a_2,…,a_n,求最少删去几个数，使得删去后这些数的最大公约数
比原先的所有数的最大公约数大。
【输入】
第一行一个整数 n，第二行 n 个正整数， a_1,a_2,…,a_n。
【输出】 一个数，表示最少删去的个数，若无论怎么删都不会比原来的大，输出-1。
【输出输出样例 1】
gcd.in
3
1 2 4
gcd.out
1
【样例 1 解释】
删去 1 这个数，最大公约数从 1 变到 2。
【输出输出样例 2】
gcd.in
4
6 9 15 30
gcd.out
2

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

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

int main() {
    int n;
    std::cin >> n;
    
    std::vector<int> nums(n);
    for (int i = 0; i < n; i++) {
        std::cin >> nums[i];
    }
    
    int maxGCD = 0;
    for (int i = 0; i < n; i++) {
        maxGCD = gcd(maxGCD, nums[i]);
    }
    
    int count = 0;
    for (int i = 0; i < n; i++) {
        if (nums[i] % maxGCD != 0) {
            count++;
        }
    }
    
    if (count == n) {
        std::cout << -1 << std::endl;
    } else {
        std::cout << count << std::endl;
    }
    
    return 0;
}