http://codeforces.com/contest/494/problem/D
题意:给一个数组，和一个坏质数集合，可以无数次地让1到i这些所有数字除以他们的gcd，然后要求Σf(a[i])的最大值，其中
f(x）=f(x/p)+1，p为x的最小质数，且p不为坏质数
f(x/p)-1 ,p为x的最小质数，且p为坏质数
思路:我们考虑，如果f[j]取了1到j的gcd，那么对后面的决策并没有任何影响，因为我们统计的贡献，只统计1到i这个部分，不统计i以后的部分。
略坑，不知道第一次被什么卡了超时。。就写哈希了。。
#include<algorithm>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<iostream>
#include<map>
#include<set>
std::map<int,int>mp;
std::set<int>b;
int n,m,f[],g[],a[];
int read(){
char ch=getchar();int t=,f=;
while (ch<''||ch>''){if (ch=='-') f=-;ch=getchar();}
while (''<=ch&&ch<=''){t=t*+ch-'';ch=getchar();}
return t*f;
}
int gcd(int a,int b){
if (b==) return a;
else return gcd(b,a%b);
}
int F(int x){
if (x<=) return ;
if (b.count(x)) return -;
int rec=x,res=;
if (mp.find(rec)!=mp.end()) return mp[rec];
int d=,cnt=;
for (int i=;i*i<=rec;i++){
int p=i;
if (x%p==){
if (b.count(p)) d=-;else d=;
while (x%p==) x/=p,cnt+=d;
}
}
if (x!=){
if (b.count(x)) d=-;else d=;
cnt+=d;
}
return (mp[rec]=cnt);
}
int main(){
n=read();m=read();
for (int i=;i<=n;i++) a[i]=read();
for (int i=;i<=m;i++) {int x=read();b.insert(x);}
int ans=;
g[]=a[];
for (int i=;i<=n;i++) g[i]=gcd(g[i-],a[i]);
for (int i=;i<=n;i++)
ans+=F(a[i]);
f[]=ans;
for (int i=;i<=n;i++){
int s=F(g[i]);
f[i]=-0x3f3f3f3f;
for (int j=i-;j>=;j--)
f[i]=std::max(f[i],f[j]-s*(i-j));
}
ans=-0x3f3f3f3f;
for (int i=;i<=n;i++) ans=std::max(ans,f[i]);
printf("%d\n",ans);
}
还有一种贪心做法，就是从后往前取，能取就取，直到变小为止。
#include<algorithm>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<iostream>
#include<map>
#include<set>
std::map<int,int>mp;
std::set<int>b;
int n,m,f[],g[],a[];
int read(){
char ch=getchar();int t=,f=;
while (ch<''||ch>''){if (ch=='-') f=-;ch=getchar();}
while (''<=ch&&ch<=''){t=t*+ch-'';ch=getchar();}
return t*f;
}
int gcd(int a,int b){
if (b==) return a;
else return gcd(b,a%b);
}
int F(int x){
if (x<=) return ;
if (b.count(x)) return -;
int rec=x,res=;
if (mp.find(rec)!=mp.end()) return mp[rec];
int d=,cnt=;
for (int i=;i*i<=rec;i++){
int p=i;
if (x%p==){
if (b.count(p)) d=-;else d=;
while (x%p==) x/=p,cnt+=d;
}
}
if (x!=){
if (b.count(x)) d=-;else d=;
cnt+=d;
}
return (mp[rec]=cnt);
}
int main(){
n=read();m=read();
for (int i=;i<=n;i++) a[i]=read();
for (int i=;i<=m;i++) {int x=read();b.insert(x);}
int ans=;
g[]=a[];
for (int i=;i<=n;i++) g[i]=gcd(g[i-],a[i]);
for (int i=;i<=n;i++)
ans+=F(a[i]);
for (int i=n;i>=;i--){
int s=F(g[i]);
if (s<){
ans-=s*i;
int t=g[i];
for (int j=;j<=i;j++)
g[j]/=t;
}
}
printf("%d\n",ans);
}