Codeforces Round #511 (Div. 2) C - Enlarge GCD (数论, 暴力)
程序员文章站
2022-05-09 16:16:52
...
题目大意
给一串数字,删除最少的数使得所有数的gcd变大
思路
先求出所有数的gcd值,然后枚举大于此gcd所有的素数,然后看有多少数的gcd是这个素数。n - cnt 就是要消去的值。
代码
#include <bits/stdc++.h>
using namespace std;
int gcd(int a, int b) {
return b ? gcd(b, a%b) : a;
}
const int inf = 0x3f3f3f3f;
const int maxn = (int)1.5e7 + 10;
bool isp[maxn];
int cnt[maxn];
void init() {
memset(isp, true, sizeof(isp));
memset(cnt, 0, sizeof(cnt));
}
int main()
{
init();
int n, ans;
scanf("%d", &n);
int v, gd = 0;
for(int i = 0; i < n; i++) {
scanf("%d", &v);
cnt[v]++;
if(gd == 0) gd = v;
else gd = gcd(gd, v);
}
isp[0] = isp[1] = false;
ans = n;
for(int i = gd + 1; i < maxn; i++) {
if(isp[i]) {
int ct = 0;
for(int j = i; j < maxn; j+=i) {
isp[j] = false;
ct += cnt[j];
}
ans = min(ans, n - ct);
}
}
if(ans == n) cout << -1 << endl;
else printf("%d\n", ans);
return 0;
}
推荐阅读
-
Orac and LCM(GCD/LCM/质因子分解/推导证明)Codeforces Round #641 (Div. 2) C题
-
Codeforces Round #512 (Div. 2,) C. Vasya and Golden Ticket【暴力】
-
Codeforces Round #511 (Div. 2)C. Enlarge GCD
-
Codeforces Round #511 (Div. 2) C. Enlarge GCD(思路,数论)
-
Codeforces Round #511 (Div. 2) C - Enlarge GCD (数论, 暴力)
-
Codeforces Round #511 (Div. 2) C. Enlarge GCD
-
【数论思维题】Enlarge GCD【Codeforces Round #511 (Div. 2)】
-
Codeforces Round #511 (Div. 2) C - Enlarge GCD(筛法)
-
Codeforces Round #511 (Div. 2) - C. Enlarge GCD(筛法)
-
Codeforces Round #511 (Div. 2)--C. Enlarge GCD