http://codeforces.com/contest/403/problem/B

You have an array of positive integers a[1], a[2], ..., a[n] and a set of bad prime numbers b1, b2, ..., bm. The prime numbers that do not occur in the set b are considered good. The beauty of array a is the sum , where function f(s) is determined as follows:

  • f(1) = 0;
  • Let's assume that p is the minimum prime divisor of s. If p is a good prime, then , otherwise .

You are allowed to perform an arbitrary (probably zero) number of operations to improve array a. The operation of improvement is the following sequence of actions:

  • Choose some number r (1 ≤ r ≤ n) and calculate the value g = GCD(a[1], a[2], ..., a[r]).
  • Apply the assignments: , , ..., .

What is the maximum beauty of the array you can get?

Input

The first line contains two integers n and m (1 ≤ n, m ≤ 5000) showing how many numbers are in the array and how many bad prime numbers there are.

The second line contains n space-separated integers a[1], a[2], ..., a[n] (1 ≤ a[i] ≤ 109) — array a. The third line contains m space-separated integers b1, b2, ..., bm (2 ≤ b1 < b2 < ... < bm ≤ 109) — the set of bad prime numbers.

Output

Print a single integer — the answer to the problem.

 

题意：给定一个n个数的序列，和m个丑素数，每个数的f()为这个数的美素数个数*1+丑素数个数*(-1)。

现允许执行若干次操作：选择r，把a[1]~a[r]全部除以gcd(a[1],a[2]...a[r])

求最大的Σ f()。

思路：可以先求出原始的f()，再考虑操作。

操作应该每次优先选尽量大的r，为什么这样呢？

这么理解，假如除a1~a5的gcd对答案的正贡献为10，负贡献为-7，合贡献为+3，这时不应该a1~a5安排掉，应该目光放长远一些，有可能a1~a10的正贡献为8，负贡献为-2，总贡献+6。然后约去gcd，发现a1~a5的正贡献为+2，负贡献为-5，不应该除a1~a5了。

故贪心策略：从右向左扫一遍，看除gcd（不算右面已经用过的因子）的贡献是不是为正，为正就采纳。

其实不从右向左扫一遍，而是暴力模拟多次操作，每次尽量区间长，也可以过。

注意：

①Q：刘汝佳的质因数分解为什么最后特判n>1？

   A：考虑任意数n，将其分解质因数为n=a*b*c*d*e...，考虑最大的两个质因数x和y，sqrt(n)>=sqrt(x*y),也就是说，sqrt(n)的位置至少是在x和y之间，这时筛到x和y之间，会留下一个最后一个质数y，特判一下。考虑上比x，y小的那些，sqrt(n)只会更大，也就是说最坏情况下最后留一个质数，一般情况下一个质数都不留。

②一个优化，相比每次sqrt(n)分解质因数，预先筛好素数的效率提升了10倍(700ms->70ms)，只需要筛sqrt(1e9)内的素数，而不需要筛整个1e9范围，因为最多n的两个因数都等于sqrt(n)，不会两个素数均大于sqrt(n)的情况出现，否则n就>1e9了。因此最多1个素数因子大于sqrt(n)，用①的最后特判就处理掉了。

#include<bits/stdc++.h>
using namespace std;

int n,m,a[6000],ans,g[6000];
set<int> ugly;
vector<int> prime;
int tot;

int gcd(int a,int b){return b==0?a:gcd(b,a%b);}

void get_prime()
{
	bool vis[100000];
	int M=sqrt(1e9+10);
	for(int i=2;i<=M;i++)if(!vis[i])
		for(int j=i*i;j<=M;j+=i)vis[j]=1;
	for(int i=2;i<=M;i++)if(!vis[i])prime.push_back(i);
	tot=prime.size();
}

int div(int n)
{
	int ret=0;
	for(int i=0;i<tot&&n>1;i++)if(n%prime[i]==0)
	{
		int num=0;
		while(n%prime[i]==0)
		{
			num++;
			n/=prime[i];
		}
		if(ugly.count(prime[i]))ret-=num;
		else ret+=num;
	}
	if(n>1)
		if(ugly.count(n))ret--;
		else ret++;
	return ret;
}

void solve()
{
	g[1]=a[1];
	for(int i=2;i<=n;i++)g[i]=gcd(g[i-1],a[i]);
	int calced=1;
	for(int i=n;i>=1;i--)
	{
		int num=div(g[i]/calced);
		if(num<0)
		{
			ans-=num*i;
			calced=g[i];
		}
	}
}

int main()
{
	//freopen("input.in","r",stdin);
	cin>>n>>m;
	int x;
	for(int i=1;i<=n;i++)scanf("%d",&a[i]);
	for(int i=1;i<=m;i++){scanf("%d",&x);ugly.insert(x);}
	get_prime();
	for(int i=1;i<=n;i++)ans+=div(a[i]);
	solve();
	printf("%d\n",ans);
	return 0;
}