C. Цувааны онцгой содон байдал

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

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

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

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

Ясин-д $n$ ширхэг бүхэл тоо агуулах $a$ цуваа байв. Ясин 5-н настай бөгөөд тэрээр онцгой содон зүйлс дуртай.

Ясин ямар нэгэн цувааны содон байдлыг бүх $1 ≤ i < j ≤ n$-уудын $gcd(a_{i},  a_{j})$ утгуудын хамгийн их утгаар тэмдэглэв. $n ≤ 1$ байвал содон байдал нь $0$-тэй тэнцүү байх бөгөөд $gcd(x,  y)$ гэдэг нь бүхэл тоо $x$ болон $y$-ын хамгийн их ерөнхий хуваагч байна.

Тэрээр мөн ямар нэгэн цувааны онцгой содон байдлыг тодорхойлжээ. Онцгой содон байдал гэдэг нь байх бөгөөд энд $f(i,  j)$ гэдэг нь $i$ болон $j$-ын хоорондох (эдгээр нь өөрсдөө мөн устгагдана) бүх элементүүдийг устган үүсэх шинэ $a$ цувааны содон байдал байна. Тодруулбал шинэ $a$ цуваа гэдэг нь $[a_{1}... a_{i - 1}, a_{j + 1}... a_{n}]$ байх юм.

5-н настай хүүхдүүд код бичиж чадахгүй учраас Ясин таныг өгөгдсөн $a$ цувааны онцгой содон байдлын утгыг олж өгөхийг хүсжээ!

Оролт

Эхний мөрөнд $a$-ын элементийн тоо болох бүхэл тоо $n$ ($1 ≤ n ≤ 200 000$) өгөгдөнө.

Дараагийн мөрөнд $n$ ширхэг бүхэл тоо $a_{i}$ ($1 ≤ a_{i} ≤ 200 000$)-ууд өгөгдөх ба эдгээрийн $i$-дахь тоо нь $a$ цувааны $i$-дахь элементтэй тэнцүү байх юм. Мөн бүх $a_{i}$-ууд нь ялгаатай байна.

Гаралт

$a$ цувааны онцгой содон байдлын утгыг агуулах ганц мөр хэвлэнэ үү.

Орчуулсан: Баатархүү

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

Оролт
3
2 6 3
Гаралт
6

Тэмдэглэл

Эхний жишээг авч үзье.

  • $f(1,  1)$=$3$.
  • $f(2,  2)$=$1$.
  • $f(3,  3)$=$2$.
  • $f(1,  2)$=$f(1,  3)$=$f(2,  3)$=$0$.

Иймд хариулт нь $3 + 0 + 0 + 1 + 0 + 2 = 6$ байна.

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