E1-G

题目要求

在[1-10^9]里等概率随机产生n个整数集，求出元素个数最大的 最大公约数大于1的数集的 元素个数

核心算法和原理

• 直接做根本做不了，所以只能从概率的角度来做

• 由于题目中n的数量至少大于616，且是等概率随机生成的，那么gcd = 2的数平均有n / 2个，而gcd = 3的数平均有n / 3个，二者之差 = n/6 > 100，故可以猜到元素个数最大的子集是gcd = 2的数集。

代码

#include <bits/stdc++.h>
using namespace std;

int a[62000];
int sum;
int main(){
    ios::sync_with_stdio(false); cin.tie(0);
    int tt;
    int n;
    cin >> tt;
    while(tt--){
        cin >> n;
        for(int i = 0; i < n; i++){
            cin >> a[i];
        }
        for(int i = 0; i < n; i++){
            if(a[i] % 2 == 0){
                sum++;
            }
        }
        cout << sum << endl;
        sum = 0;
    }
    return 0;
}