CodeForces 402D-Upgrading Array

D. Upgrading Array

time limit per test1 second

memory limit per test256 megabytes

You have an array of positive integers a1,a2,...,an a 1 ,   a 2 ,   . . . ,   a n and a set of bad prime numbers b1,b2,...,bm b 1 ,   b 2 ,   . . . ,   b m . 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; f ( 1 )   =   0 ;
• Let’s assume that p p is the minimum prime divisor of ss. If p p is a good prime, then f(s)=f(sp+1)f(s)=f(sp+1), otherwise f(s)=f(sp−1) f ( s ) = f ( s p − 1 ) .

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) r ( 1   ≤   r   ≤   n ) and calculate the value g=GCD(a1,a2,...,ar) g = G C D ( a 1 ,   a 2 ,   . . . ,   a r ) .

• Apply the assignments: a1=a1g,a2=a2g,...,ar=arg a 1 = a 1 g , a 2 = a 2 g , . . . , a r = a r g .

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

Input

The first line contains two integers n n and mm (1≤n,m≤5000) ( 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 n space-separated integers a[1],a[2],...,a[n](1≤a[i]≤109)a[1], a[2], ..., a[n](1 ≤ a[i] ≤ 109) — array a. The third line contains m m space-separated integers b1,b2,...,bmb1, b2, ..., bm (2≤b1<b2<...<bm≤109) ( 2   ≤   b 1   <   b 2   <   . . .   <   b m   ≤   10 9 ) — the set of bad prime numbers.

Output

Print a single integer — the answer to the problem.

Examples

input1

5 2

4 20 34 10 10

2 5

output1

-2

input2

4 5

2 4 8 16

3 5 7 11 17

output2

10

Note

Note that the answer to the problem can be negative.

The GCD(x1,x2,...,xk) G C D ( x 1 , x 2 , . . . , x k ) is the maximum positive integer that divides each xi.

Soluion

use g[i] g [ i ] denoting gcd(a1,a2,...,an) g c d ( a 1 , a 2 , . . . , a n ) ,so we can find that array g g is a unincreasing array.

Also,g[i]g[i]must be a divisor of g[i−1] g [ i − 1 ] .That’s obviously we do from the tail to the head is better(For the latter prefix gcd g c d do not impact the gcd g c d in the front).

if delete the prefix gcd g c d can add the beauty of the array,we divide it.

But how can we get the f[a[i]] f [ a [ i ] ] ???

Clearly,Pretreatment comes.We can pretreat the primes less than max(a[i])‾‾‾‾‾‾‾‾‾√ m a x ( a [ i ] ) and put the bad primes into hash,so we can get whether a prime is good or not in time O(1) O ( 1 ) .

Code

#include <cstdio>
#include <algorithm>
#include <math.h>
#define N 5010
#define PSC 6974895
#define P 32000
#define DB printf("......\n")

using namespace std;
int hash[PSC], a[N], g[N], p[P], cnt;
bool pr[P];

int gcd(int x, int y) {
    if (y == ) return x;
    return gcd(y, x % y);
}

inline void hash_ins(int x) {
    int o = x % PSC;
    while(hash[o] > ) {
        o++;
        if (o == PSC) o -= PSC;
    }
    hash[o] = x;
}

inline bool hash_que(int x) {
    int o = x % PSC;
    while(hash[o] > ) {
        if (hash[o] == x) return ;
        o++;
        if (o == PSC) o -= PSC;
    }
    return ;
}

int main() {
    int n, m, maxa = ;
    scanf("%d%d", &n, &m);
    for (int i = ; i <= n; ++i) {
        scanf("%d", &a[i]);
        maxa = max(maxa, a[i]);
    }
    for (int i = ; i <= m; ++i) {
        int x;
        scanf("%d", &x);
        hash_ins(x);
    }
    maxa = (int)sqrt(maxa) + ;
    for (int i = ; i * i <= maxa; ++i)
        if (!pr[i])
            for (int j = ; j * i <= maxa; ++j)
                pr[i * j] = ;
    for (int i = ; i <= maxa; ++i)
        if (!pr[i]) p[++cnt] = i;
    int ans = ;
    for (int i = ; i <= n; ++i) {
        int o = a[i];
        for (int j = ; p[j] * p[j] <= a[i] && j <= cnt; ++j) {
            int num = ;
            while(o % p[j] == ) {
                o /= p[j];
                num++;
            }
            if (hash_que(p[j])) ans -= num;
            else ans += num;
        }
        if (o > ) {
            if (hash_que(o)) ans--;
            else ans++;
        }
    }
    g[] = a[];
    int i;
    for (i = ; i <= n; ++i) {
        g[i] = gcd(g[i - ], a[i]);
        if (g[i] == ) break;
    }
    int di = ;
    for (i = i - ; i >= ; --i) {
        int l = g[i] / di, now = , o = l;
        for (int j = ; p[j] * p[j] <= l && j <= cnt; ++j) {
            int num = ;
            while (o % p[j] == ) {
                o /= p[j];
                num++;
            }
            if (hash_que(p[j])) now -= num;
            else now += num;
        }
        if (o > ) {
            if (hash_que(o)) now--;
            else now++;
        }
        if (now < ) {
            ans -= now * i;
            di *= l;
        }
    }
    printf("%d\n", ans);
    return ;
}