题目链接：http://codeforces.com/problemset/problem/402/D
题意：
给你一个长度为n的数列a[i]，又给出了m个“坏质数”b[i]。
定义函数f(s)，其中p是s的最小质因子:
f(1) = 0
f(s) = f(s/p) + 1 （p不是坏质数）
f(s) = f(s/p) - 1 （p是坏质数）
你可以任意次数地进行操作：给a[1 to i]的每个数都除以gcd(a[1 to i])。
问你 ∑ f(a[i)最大为多少。
题解：
函数f(s)的实际意义是：
s的质因子中，好质数的个数 - 坏质数的个数。
每一次操作的实际意义是：
对于所选前缀中的每个数，从它的质因子中丢掉若干个好质数和坏质数。
显然，要想使 ∑ f(a[i)更大，则：
对于每次操作，当且仅当丢掉的坏质数的个数大于丢掉好质数的个数时，才会执行操作。
然后考虑操作顺序所带来的影响：
假设有i < j。
如果先执行操作opt(1 to i)，再执行操作opt(1 to j)：
由于第一次操作已经使得gcd(a[1 to i])变为1，并且区间[1,j]包含着[1,i]。
所以此时gcd(a[1 to j]) = 1，即第二次操作是无效的。
也就是说，a[i+1 to j]中的一些数，本身可以对答案做出贡献，却因为第一次操作而失效。
如果先执行操作opt(1 to j)，再执行操作opt(1 to i)：
因为第一次操作已经将a[i+1 to j]中可以除掉的坏质数全部除掉，并将a[1 to i]中的一部分坏质数除掉。
所以在第二次操作时，只要将a[1 to i]中剩下的坏质数除掉即可，不会有任何浪费。
所以从后往前贪心地操作就好啦。
复杂度分析：
（1）预处理出前缀gcd[i]：
O(n*logn)
（2）处理出所有操作完成后的数列a[i]（要分解质因数）：
O(n*sqrt(n))
（3）算出所有的f(a[i])（还要分解质因数）：
O(n*sqrt(n))
AC Code:
#include <iostream>
#include <stdio.h>
#include <string.h>
#include <math.h>
#include <set>
#define MAX_N 5005 using namespace std; int n,m;
int a[MAX_N];
int g[MAX_N];
set<int> st; void read()
{
cin>>n>>m;
for(int i=;i<=n;i++)
{
cin>>a[i];
}
int x;
for(int i=;i<=m;i++)
{
cin>>x;
st.insert(x);
}
} int gcd(int a,int b)
{
return b== ? a : gcd(b,a%b);
} void cal_g()
{
g[]=a[];
for(int i=;i<=n;i++)
{
g[i]=gcd(g[i-],a[i]);
}
} pair<int,int> cal_p(int x)
{
int good=;
int bad=;
for(int i=,t=sqrt(x);i<=t;i++)
{
int cnt=;
while(x%i==)
{
x/=i;
cnt++;
}
if(cnt)
{
if(st.count(i)>) bad+=cnt;
else good+=cnt;
}
}
if(x!=)
{
if(st.count(x)>) bad++;
else good++;
}
return pair<int,int>(good,bad);
} bool check(int x)
{
pair<int,int> p=cal_p(x);
return p.first<p.second;
} void cal_a()
{
int d=;
for(int i=n;i>=;i--)
{
if(check(g[i]/d)) d=g[i];
a[i]/=d;
}
} int cal_f()
{
int ans=;
for(int i=;i<=n;i++)
{
pair<int,int> p=cal_p(a[i]);
ans+=p.first-p.second;
}
return ans;
} void work()
{
cal_g();
cal_a();
cout<<cal_f()<<endl;
} int main()
{
read();
work();
}