# CFR 402 D. Upgrading Array ( Greedy )

Problem - D - Codeforces

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] ≤ 1e9) — array a. The third line contains m space-separated integers b1, b2, ..., bm (2 ≤ b1 < b2 < ... < bm ≤ 1e9) — the set of bad prime numbers.
TL: 1000 ms
ML: 256 MB

O( N^1.5 * lg M )

```int N, M;
vi A;
vi B;

void init(){
cin >> N >> M;
A = vi( N );
for( int i = 0; i < N; ++i ){
cin >> A[ i ];
}
B = vi( M );
for( int i = 0; i < M; ++i ){
cin >> B[ i ];
}
}

vi pgcd;

void preprocess(){
pgcd = vi( N + 1 );
for( int i = 0; i < N; ++i ){
pgcd[ i + 1 ] = __gcd( pgcd[ i ], A[ i ] );
}
for( int i = 0; i < M; ++i ){
}
}

int evaluate( int v ){
int res = 0;
for( int i = 2; i * i <= v; ++i ){
while( v % i == 0 ){
v /= i;
--res;
} else{
++res;
}
}
}
if( v > 1 ){
--res;
} else{
++res;
}
}
return res;
}

void solve(){
ll ans = 0LL;
int del = 1;
for( int i = N; i >= 1; --i ){
int v = evaluate( pgcd[ i ] / del );
if( v < 0 ){
del = pgcd[ i ];
}
ans += evaluate( A[ i - 1 ] / del );
}
cout << ans << endl;
}
```