acwing4083. 最大公约数

给定一个长度为 nn 的整数序列 a1,a2,…,ana1,a2,…,an。
请你从中选出尽可能多的数。
要求满足如下两个条件之一：

• 仅选择一个数；
• 选择至少两个数，且所选择的数的最大公约数大于 11；

输出选出数的最大可能数量。

输入格式

第一行包含整数 nn。
第二行包含 nn 个整数 a1,a2,…,ana1,a2,…,an。

输出格式

一个整数，表示选出数的最大可能数量。

数据范围

前 66 个测试点满足 1≤n≤101≤n≤10。
所有测试点满足 1≤n≤1051≤n≤105，1≤ai≤1051≤ai≤105。

输入样例1：

3 2 3 4

输出样例1：

2

输入样例2：

5 2 3 4 6 7

输出样例2：

3

#include<iostream>
using namespace std;
const int N = 100010;
int n;
int cnt[N];
int main(){
    cin >> n;
    while(n--){
        int x;
        cin >> x;
        cnt[x]++;
    }
    int res = 1;
    for(int d = 2; d <= N; ++d){
        int t = 0;
        for(int j = d; j <= N; j += d){
            t += cnt[j];
        }
        res = max(res,t);
    }
    cout << res << endl;
    return 0;
}