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

{
}

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

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