【数论思维题】Enlarge GCD【Codeforces Round #511 (Div. 2)】
程序员文章站
2022-05-09 16:16:40
...
题意:
给你 n 个数,分别为 a1、a2、...、ai、... an,现在从这n个数中删去p个数,使剩下的数的gcd变大。求最小的p。
思路:
一开始的思路是想用贪心做,先求出所有数字的gcd,然后将数字排序,再依次求gcd,如果与当前这个数字求出的gcd等于开始的那个gcd,就将这个数字删掉。
然后wa 8,很明显这个方法是错的,比如 2 4 7 14 21 这个序列,用这种方法就会出错。
接下来是正解。N = 1.5*1e7。
先对所有数求出gcd,然后对1-N内所有数进行标记,若题目中给出了 a[i],则 vis[a[i]]++,然后采用一种类似埃氏筛的方法。
i 从gcd+1到N进行循环,对于p[i] == 0,就将 i 的所有倍数k,p[k]标记为1,然后记录 i 的所有倍数中有cnt个在最开始题目给出的数列中出现了,那么对于这cnt个数,他们的gcd一定大于初始数列的gcd,因此问题就转化为了求cnt的最大值。
本问题就解决了。
反思:
这道题拿到手上之后,思路先是跑到了最简单的贪心,然后wa了之后,开始将每个数唯一分解进行筛数,与正解思想类似,但是正解是用所有数去筛,而唯一分解是用素数去筛,过了评测,但是终测挂了。
结束之后看到正解之后还是有一些小遗憾的,毕竟正解代码非常短......(比唯一分解什么的短多了......)
以后写题还是要考虑清楚,不要进行冗余操作,也不要漏操作。
代码:
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#define rep(i,a,b) for(int i = a;i <= b;i++)
using namespace std;
const int N = 1.5*1e7+1000;
int a[N],b[N];
int n;
int gcd(int a,int b)
{
return b == 0 ? a:gcd(b,a%b);
}
int main()
{
int d;
scanf("%d",&n);
scanf("%d",&d);
a[d]++;
rep(i,2,n){
int x;
scanf("%d",&x);
a[x]++;
d = gcd(d,x);
}
int ans = 0;
rep(i,d+1,N-500)
{
if(b[i] == 0)
{
int cnt = 0;
for(int j = i; j <= N-500; j += i)
{
b[j] = 1;
cnt += a[j];
}
ans = max(ans,cnt);
}
}
if(ans == 0)
printf("-1\n");
else printf("%d\n",n-ans);
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
-
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)】