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

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
//==========================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;
}

------ 本文结束 ------