403B

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;
}