403B


  Posted on 16 Dec 2014
greedy number theory

Solution


#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>
using namespace std;

#define D(x) 

const int MAX_N = int(1e4);
const int MAX_M = int(1e4);

int n, m;
int value[MAX_M];
int bad[MAX_N];
int gcd_array[MAX_N];

int gcd(int a,int b){
    if (a==0) return 1;
    if (a<0) return gcd(-a,b);
    while (b){
	int t=a%b; a=b; b=t;
    }
    return a;
}

bool is_bad(int a)
{
	return a == *lower_bound(bad, bad + m, a);
}

int cal(int a)
{
	D(printf("%d ", a));
	int ret = 0;
	for (int i = 2; i * i <= a; i++)
	{
		while (a % i == 0)
		{
			if (is_bad(i))
				ret--;
			else
				ret++;
			a /= i;
		}
	}
	if (a == 1)
	{
		D(printf("%d\n", ret));
		return ret;
	}
	if (is_bad(a))
		ret--;
	else
		ret++;
	D(printf("%d\n", ret));
	return ret;
}

int main()
{
	//input
	scanf("%d%d", &n, &m);
	for (int i = 0; i < n; i++)
	{
		scanf("%d", &value[i]);
	}
	for (int i = 0; i < m; i++)
	{
		scanf("%d", &bad[i]);
	}

	//work
	int temp = value[0];
	for (int i = 0; i < n; i++)
	{
		temp = gcd(temp, value[i]);
		gcd_array[i] = temp;
	}
	temp = 1;
	for (int i = n - 1; i >= 0; i--)
	{
		if (cal(gcd_array[i] / temp) < 0)
		{
			temp = gcd_array[i];
		}
		value[i] /= temp;
	}

	int ans = 0;
	for (int i = 0; i < n; i++)
	{
		ans += cal(value[i]);
	}
	printf("%d\n", ans);
	return 0;
}