CF671C Ultimate Weirdness of an Array

Yasin 有一个包含 $n$ 个整数的数组 $a$。Yasin 只有 5 岁，所以他喜欢极其奇怪的东西。 Yasin 定义一个数组的“怪异度”为所有 $1 \leq i < j \leq n$ 中 $gcd(a_i, a_j)$ 的最大值。如果 $n \leq 1$，怪异度定义为 $0$。这里，$gcd(x,y)$ 表示整数 $x$ 和 $y$ 的最大公约数。 他还定义了数组的“终极怪异度”。终极怪异度为 $$ \sum_{1 \leq i \leq j \leq n} f(i, j) $$ 其中 $f(i, j)$ 表示将 $a$ 中从第 $i$ 个到第 $j$ 个（包含 $i$ 和 $j$）元素都删除后，剩下的新数组的怪异度。新数组为 $[a_1, a_2, ..., a_{i-1}, a_{j+1}, ..., a_n]$。 由于 5 岁的小孩不会写代码，Yasin 请你帮助他求出给定数组 $a$ 的终极怪异度值！

输入的第一行包含一个整数 $n$（$1 \leq n \leq 200000$），表示数组 $a$ 的元素个数。 输入的第二行包含 $n$ 个整数 $a_i$（$1 \leq a_i \leq 200000$），其中第 $i$ 个数表示 $a$ 的第 $i$ 个元素。保证所有 $a_i$ 互不相同。

输出一行，表示数组 $a$ 的终极怪异度。

以第一个样例为例： - $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$。 由 ChatGPT 5 翻译