贪心

admin管理员组

文章数量:1516870

贪心

题目大意：
给定n 个数ai，以及大小为m 的质数集合bi.
定义f 函数：f(1) = 0. 令p 为s 的最小质因子，若p 不在b 中，则f(s) = f(s/p) + 1，否则f(s)=f(s/p)- 1
现在你可以对a 做任意次操作，每次操作可以选择一个r，使得
a1; a2; ; ar 同除以g，g = GCD(a1; a2;···; ar)，求通过操作后能得到的f（a[i]）和的最大值

solution：
一个r 只能操作一次
令Gr = GCD(a1; a2; ; ar)，显然Gi | Gj(i > j)
因此若选择i 操作，则j(j > i) 都无法执行，且操作j(j > i) 的影响也包含在i 中
从n 开始一位位贪心，若操作能增大答案就执行操作
正确性：若当前能增大答案不选择增大，则若之后都不进行操作，
显然不优；若之后进行操作，则当前执行操作的影响也被包含在其
中，注意贡献是可减的，所以在当前位置操作不会更劣
计算贡献时暴力根号分解数字即可
O(n *sqrt(10^9))

实现也还是比较麻烦的
首先因为时限紧需要筛一下素数
然后注意到ai和bi都是10^9级别的，因此不能把每个f都记下来
考虑f递推的过程，每个数的f值都可以由其质因子得出
所以可以写一个f函数专门计算
每次考虑每个gcd除掉能不能增大答案也是用这个f函数判断
为了方便可以将b存成set可以查询
还有一些细节问题具体看代码

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<set>
#define maxn 5005
#define LL long long
using namespace std;
const int N=1e6+5;
int n,m,a[maxn],pri[N],cnt;
bool vis[N];
LL ans,g[maxn],qwq=1;
set<int> b;inline int rd(){int x=0,f=1; char c=' ';while(c<'0' || c>'9') {if(c=='-') f=-1;c=getchar();}while(c<='9' && c>='0') x=x*10+c-'0',c=getchar();return x*f;
}void get_prime(){for(int i=2;i<=N;i++){if(!vis[i]) pri[++cnt]=i;for(int j=1;j<=cnt && i*pri[j]<=N;j++){vis[i*pri[j]]=1;if(i%pri[j]==0) break;}}
}inline LL gcd(LL x,LL y){return y==0?x:gcd(y,x%y);
}int f(int x){if(x<=1) return 0;int ret=0;for(int i=1;i<=cnt && pri[i]<=sqrt(x);i++)while(x%pri[i]==0){x/=pri[i];if(b.find(pri[i])==b.end()) ret++;else ret--;}if(x>1)if(b.find(x)==b.end()) ret++;else ret--;return ret;
}int main(){n=rd(); m=rd();for(int i=1;i<=n;i++) a[i]=rd();for(int i=1;i<=m;i++) {int x=rd();b.insert(x);}get_prime();g[1]=a[1];for(int i=2;i<=n;i++){g[i]=gcd(g[i-1],a[i]);}for(int i=n;i>=1;i--){int tmp=f(g[i]/qwq);if(tmp<0) qwq=g[i];a[i]/=qwq;}for(int i=1;i<=n;i++) ans+=f(a[i]);printf("%lld\n",ans);return 0;
}

本文标签： 贪心