Codecraft-17 and Codeforces Round #391 (Div. 1 + Div. 2, combined) B. Bash’s Big Day 数论+贪心

My Solution

题意：给出n个数，选出尽可能多的数，使这些数的gcd不是1.

数论+贪心

选出尽可能多的数，使这些数的gcd不是1.，则它们的gcd是x，x >= 2,

所以可以枚举gcd的值，从2到1e5，然后枚举倍数 j， x * j (x*j < 1e5)必定在x的集合里所以1<=j <=1e5 ，

即对于每个i 最多可以枚举j = 1e5 / i 个值i * j，故对于1e5 / x 从1 到1e5积分，得n*lin(n) 约等于 1e6

故复杂度 O(nln(n))

#include 
#include 
#include 
using namespace std;
typedef long long LL;
const LL maxn = 1e5 + 8;

int cnt[maxn];

int main()
{
    #ifdef LOCAL
    freopen("b.txt", "r", stdin);
    //freopen("b.out", "w", stdout);
    int T = 4;
    while(T--){
    #endif // LOCAL
    ios::sync_with_stdio(false); cin.tie(0);

    int n, a;
    cin >> n;
    for(int i = 0; i < n; i++){ cin >> a;
        cnt[a]++;
    }

    LL i, j, k, ans = 1;
    //直接 1e5/x从1到1e5积分等于1e6
    for(i = 2; i < maxn; i++){
        k = 0;
        for(j = 1; j <= maxn; j++){
            if(i * j < maxn){
                k += cnt[i * j];
            }
            else break;
        }
        ans = max(ans, k);

    }
    cout << ans << endl;

    #ifdef LOCAL
    memset(cnt, 0, sizeof cnt);
    cout << endl;
    }
    #endif // LOCAL
    return 0;
}

非特殊说明，本博所有文章均为博主原创，未经许可不得转载。

https://www.prolightsfxjh.com/

Thank you!

                                                                                                                                             ------from ProLightsfx