CF1034A
[TOC]
题意
给你n个数,求最少去掉几个数能让这些数的最大公因数变大
输入
第一行给出一个n(2<=n<=3e5)
第二行给出n个数,表示a1,a2….an,其中ai表示第i个数
输出
输出最少删掉的数
解析
关于一堆数的最大公约数,思路还是唯一分解定理.然后我们发现对于每个质因数,似乎只要把为0的去掉就可以了,但是!!!
如果
a = 2^1 * 3^0
b = 2^3 * 3^0
c = 2^3 * 3^1
我们就悲剧地发现,最好的策略应该是去掉a,但是根据刚才的思路,是应该去掉a和b,所以这样就对这个问题的求解产生了极大不便利,因为实际上的策略应该是对每一个质因数计算其最小的指数的数个数,然后在所有质因数中选一个数量最小的,然后就得到了答案,但是我们发现,由于对于每个质因数,其要求的最小的指数不一样,比如刚才的例子,2的最小指数是1,而3的最小指数是0,所以我们将所有的质因数的最小指数都变成0
其方法很简单,就是求出所有数的最大公因数,然后将所有数都除最大公因数,这样就使得所有质因数的最小指数都变成了0.然后对我们来说,我们只考虑对于某个质因数的指数是否是零(说的有点乱,看代码)
代码
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
98
99
100
101
102
103
// CF1034A
#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
#include <map>
#include <set>
#include <cstring>
#include <string>
#include <cstdio>
#include <cmath>
using namespace std;
void ioInit() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
}
int a[300100];
const int N = 15000 + 5;
bool prime[N];//prime[i]表示i是不是质数
int p[N], tot;//p[N]用来存质数
int cntP[15000005];
int gcd(int a, int b) {
return b ? gcd(b, a % b) : a;
}
void init() { // 线性筛,每个数只会被筛掉一次
for (int i = 2; i < N; i++)
prime[i] = true;//初始化为质数
for (int i = 2; i < N; i++) {
if (prime[i]) p[tot++] = i;//把质数存起来
for (int j = 0; j < tot && i * p[j] < N; j++) {
prime[i * p[j]] = false;
if (i % p[j] == 0) break;//保证每个合数被它最小的质因数筛去
}
}
}
int maxj = 0;
void CntPrime(int n) {
for (int i = 0; i < tot && p[i] * p[i] <= n; ++i) {
if (n % p[i] == 0) {
++cntP[p[i]]; // n的质因数分解中,p[i]的指数不是零
maxj = max(maxj, p[i]);
while (n % p[i] == 0) {
n /= p[i];
}
/*
在此处就得到了 质因子 prime[i] 和 其幂 cnt,这里就可以进行很多操作了,此处以举例为目的,故仅数出来质因子个数
*/
}
}
if (n >
1) { // 注意这种情况,结合上文代码考虑,这种情况是指n排除了所有小于等于√n的因子之后,仍然还有因子的情况,可想而知,大于√n的因子绝对不超过一个,(因为两个大于√n的因子相乘其结果一定大于n),所以如果有这种因子的话,其个数一定为1(事实上此时的n就是这个因子)
++cntP[n]; // 同理
maxj = max(maxj, n);
}
}
int main() {
// ioInit();
init();
int n;
scanf("%d", &n);
//cin >> n;
int g = 0;
for (int i = 0; i < n; ++i) {
scanf("%d", &a[i]);
//cin >> a[i];
if (i) {
g = __gcd(g, a[i]);
} else {
g = a[0];
}
}
if (g != 1)
for (int i = 0; i < n; ++i) {
a[i] /= g;
}
for (int i = 0; i < n; ++i) {
CntPrime(a[i]);
}
int ans = 0;
cerr << maxj << endl;
for (int i = 0; i <= maxj; ++i) { // 选指数最多的最后用n减,实际上和直接选指数最少的也是一个道理
ans = max(ans, cntP[i]);
// cerr << cntP[p[i]] << endl;
}
if (!ans) {
printf("-1\n");
} else {
printf("%d\n", n - ans);
}
return 0;
}
