D. Дарааллыг сайжруулах

хугацааны хязгаарлалт 1 секунд

санах ойн хязгаарлалт 256 мегабайт

оролт стандарт оролт

гаралт стандарт гаралт

Чамд эерэг бүхэл тоон дараалал $a_1, a_2, ..., a_n$ ба муу анхны тоонуудын олонлог $b = \{b_{1}, b_{2}, ..., b_{m}\}$ өгөгджээ. $b$ олонлогт ордоггүй анхны тоонуудыг сайн анхны тоонууд гэе. $a$ дарааллын чанар гэдэг ойлголтыг $\sum\limits_{i=1}^{n} f(a_i)$ гэж тодорхойлъё. Энд $f(s)$ функц нь дараахь байдлаар тодорхойлогдоно:

  • $f(1) = 0$;
  • $p$ нь $s$-ийн хамгийн бага анхны тоон хуваагч байг. Хэрэв $p$ сайн анхны тоо бол $f(s) = f(\frac{s}{p}) + 1$, үгүй бол $f(s) = f(\frac{s}{p}) - 1$.

Чи $a$ дарааллын чанарыг сайжруулахын тулд хэдэн ч үйлдэл хийж болно. Чанарыг сайжруулах үйлдэл гэдэг нь дараах үйлдлүүдийн дараалал юм:

  • $r$ ($1 ≤ r ≤ n$) гэсэн тоо сонгоод $g$ = $GCD(a_1, a_2, ..., a_r)$ утгыг олно.
  • Дараа нь эдгээрт шинэ утга олгоно: $a_1 = \frac{a_1}{g}, a_2 = \frac{a_2}{g}, ... , a_r = \frac{a_r}{g}$.

Та уг дарааллын чанарыг хамгийн ихдээ хэд болгож чадах вэ?

Оролт

Эхний мөрөнд дарааллын урт болон муу анхны тоонуудын тоог илэрхийлэх $n$ ба $m$ ($1 ≤ n, m ≤ 5000$) бүхэл тоонууд өгөгдөнө.

Хоёр дахь мөрөнд $a$ дарааллын гишүүд $a_1, a_2, ..., a_n$ ($1 ≤ a[i] ≤ 10^{9}$) нар зайгаар тусгаарлагдан өгөгдөнө.

Гурав дахь мөрөнд муу анхны тоонууд болох $b_{1}, b_{2}, ..., b_{m}$ ($2 ≤ b_{1} < b_{2} < ... < b_{m} ≤ 10^{9}$) тоонууд зайгаар тусгаарлагдан өгөгдөнө.

Гаралт

Бодлогын хариуг хэвлэ.

Орчуулсан: Бат-Од

Жишээ тэстүүд

Оролт
5 2
4 20 34 10 10
2 5
Гаралт
-2
Оролт
4 5
2 4 8 16
3 5 7 11 17
Гаралт
10

Тэмдэглэл

Бодлогын хариу сөрөг тоо байж болохыг анхаарна уу.

$GCD(x_{1}$, $x_{2}$, ..., $x_{k})$ гэдэг нь $x_{i}$ бүрийг хуваадаг хамгийн том тоог илэрхийлнэ.

Сэтгэгдлүүдийг ачааллаж байна...