Codeforces Round #511 (Div. 2) C. Enlarge GCD (思维题)
程序员文章站
2022-05-09 16:16:28
...
原题地址:http://codeforces.com/contest/1047/problem/C
题意:给出n个数字,现在询问你最少需要删除多少个数字使得剩余数字的gcd会增大,如果不能不能就输出-1
思路:我们考虑先求出所有数字的gcd,然后再让每一个数字除这个gcd,那么除完之后的序列的gcd必定为1.那么如果这些数字全部是1,那么必然不能使得gcd变大.否则的话,我们只需要记录每一个数字的有哪些质因数,然后去寻找出现最多的那个质因子就行了.
#include <bits/stdc++.h>
#define eps 1e-8
#define INF 0x3f3f3f3f
#define PI acos(-1)
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
#define CLR(x,y) memset((x),y,sizeof(x))
#define fuck(x) cerr << #x << "=" << x << endl
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int seed = 131;
const int maxn = 3e5 + 5;
const int mod = 1e9 + 7;
int n;
int a[maxn];
const int mx = 15e6 + 5;
int noprime[mx], pcnt, p[mx]; //p存的是质数
void getprime(int N) {
pcnt = 0;
memset(noprime, 0, sizeof(noprime));//1表示是质数
noprime[0] = noprime[1] = 1;
for (int i = 2; i < N; ++i) {
if (!noprime[i]) {
noprime[i] = i; //表示数字i是第几个质数,3会是1,需要特判
p[pcnt++] = i;//p是存的所有质数
}
for (int j = 0; j < pcnt && i * p[j] < N; ++j) {
noprime[i * p[j]] = p[j];//i*p[j]有一个质因子是p[j]
if (i % p[j] == 0)break;
}
}
}
int num[mx];
int main() {
scanf("%d", &n);
getprime(15e6 + 3);
int flag = 0;
for (int i = 1; i <= n; i++) {
scanf("%d", &a[i]);
}
int gcd = 0;
for (int i = 1; i <= n; i++) gcd = __gcd(gcd, a[i]);
for (int i = 1; i <= n; i++) {
a[i] /= gcd;
if (a[i] != 1) flag = 1;
}
for (int i = 1; i <= n; i++) {
while (a[i] != 1) {
int x = noprime[a[i]];
num[x]++;
while (a[i] % x == 0) {
a[i] /= x;
}
}
}
if (!flag) {
printf("-1\n");
return 0;
}
int MIN = INF;
for (int i = 0; i < mx; i++) {
MIN = min(MIN, n - num[p[i]]);
}
printf("%d\n", MIN);
return 0;
}
推荐阅读
-
Codeforces Round #482 (Div. 2) D. Kuro and GCD and XOR and SUM(数学+01字典树)(好题)
-
Educational Codeforces Round 60 (Rated for Div. 2) ----A - Best Subsegment(思维题)
-
构造思维+树形结构 Codeforces Round #612 (Div. 2) D题 Numbers on Tree
-
Orac and LCM(GCD/LCM/质因子分解/推导证明)Codeforces Round #641 (Div. 2) C题
-
Codeforces Round #261 (Div. 2)C题(思维题)_html/css_WEB-ITnose
-
Educational Codeforces Round 106 (Div. 2) C. Minimum Grid Path(思维 枚举 贪心)
-
Educational Codeforces Round 48 (Rated for Div. 2) C. Vasya And The Mushrooms(思维)
-
Codeforces Round #511 (Div. 2)C. Enlarge GCD
-
Codeforces Round #511 (Div. 2) C. Enlarge GCD(思路,数论)
-
Codeforces Round #511 (Div. 2) C - Enlarge GCD (数论, 暴力)