Codeforces 1047C(数论GCD+质因数+线性筛)

发表于 | 分类于 | | + s

Codeforces 1047C
题意：给你一个序列，你需要删除其中一些数使得序列GCD比原序列GCD大。
将所有数除以 GCD，然后现在对数进行质因数分解，那么每个质因子都可以乘回 原序列GCD 然后比 原序列GCD 大。但是质因数分解这里时间不太够，我们可以线性筛，用质数去找它的倍数，统计一下有几个数在序列中，越多越好，这样删的数就越少
(我数论太弱了，筛选都不会，GG
知识点：
1、线性筛时间复杂度大约$O(nlog(logn))$
2、将数字除以 GCD 数很好的思路

//==========================Head files==========================
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<queue>
#include<cmath>
#include<map>
#include<iostream>
#define LL long long
#define db double
#define mp make_pair
#define pr pair<int, int>
#define fir first
#define sec second
#define pb push_back
#define ms(i, j) memset(i, j, sizeof i)
using namespace std;
//==========================Templates==========================
inline int read() {
    int x = 0, f = 1; char c = getchar();
    while(c < '0' || c > '9'){if (c == '-') f = -1; c = getchar();}
    while(c >= '0' && c <= '9'){x = x * 10 + c - '0'; c = getchar();}
    return x * f;
}
inline LL readl() {
    LL x = 0, f = 1; char c = getchar();
    while(c < '0' || c > '9'){if (c == '-') f = -1; c = getchar();}
    while(c >= '0' && c <= '9'){x = x * 10 + c - '0'; c = getchar();}
    return x * f;
}
int power(int a, int b) {
    int ans = 1;
    while (b) {
        if(b & 1) ans = ans * a;
        b >>= 1; a = a * a;
    }
    return ans;
}
int power_mod(int a, int b, int mod) {
    a %= mod;
    int ans = 1;
    while (b) {
        if(b & 1) ans = (ans * a) % mod;
        b >>= 1, a = (a * a) % mod;
    }
    return ans;
}
LL powerl(LL a, LL b) {
    LL ans = 1ll;
    while (b) {
        if(b & 1ll) ans = ans * a;
        b >>= 1ll;a = a * a;
    }
    return ans;
}
LL power_modl(LL a, LL b, LL mod) {
    a %= mod;
    LL ans = 1ll;
    while (b) {
        if(b & 1ll) ans = (ans * a) % mod;
        b >>= 1ll, a = (a * a) % mod;
    }
    return ans;
}
LL gcdl(LL a, LL b) {return b == 0 ? a : gcdl(b, a % b);}
LL abssl(LL a) {return a > 0 ? a : -a;}
int gcd(int a, int b) {return b == 0 ? a : gcd(b, a % b);}
int abss(int a) {return a > 0 ? a : -a;}
//==========================Main body==========================
#define LD "%I64d"
#define D "%d"
#define pt printf
#define sn scanf
#define pty printf("YES\n")
#define ptn printf("NO\n")
//==========================Code here==========================

LL n, a[300000 + 5];
LL fac[15000000 + 5], vis[15000000 + 5], g = 0ll, mks = 0ll;

int main() {
    ms(fac, 0), ms(vis, 0);
    cin >> n;
    for (LL i = 1; i <= n; i++) scanf("%lld", &a[i]), g = gcdl(a[i], g);
    for (LL i = 1; i <= n; i++) a[i] /= g, fac[a[i]]++, mks = max(mks, a[i]);
    LL ans = 0;
    for (LL i = 2; i <= mks; i++) {
        LL tmp = 0ll;
        if (!vis[i]) for (LL j = i; j <= mks; j += i) {
            vis[j] = 1, tmp += fac[j];
        }
        ans = max(ans, tmp);
    }
    if (ans == 0) cout << -1; else cout << n - ans;
    return 0;
}
------ 本文结束 ------